Рассказываем о неравенстве P≠NP и недавней попытке его доказать

N+1Наука

Удаленное доказательство

Рассказываем о неравенстве P ≠ NP и недавней попытке его доказать

Владимир Потапов

Из семи Задач тысячелетия до сих пор решена только одна — гипотеза Пуанкаре, доказательство которой сформулировал Григорий Перельман. В начале сентября появились сообщения, что американский математик Мартин Доуд (Martin Dowd) справился с еще одной задачей из списка, сумев доказать неравенство классов P и NP. Но через пару недель математик удалил статью с доказательством. Мы попросили рассказать Владимира Потапова из Института математики имени Соболева СО РАН, что с доказательством Доуда было не так, и почему неравенство P и NP так важно.

Проблема, которую принято кратко записывать формулой «P ≠ NP?», пожалуй, вторая по числу опубликованных неверных решений после Великой теоремы Ферма и первая из до сих пор нерешенных. Почему эта проблема привлекает внимание множества математиков и даже совсем не математиков? Что означает ее решение для математики и для человечества?

Что такое «сложно»?

Начнем издалека — с понятия сложности. Точнее не сложности вообще, а более конкретно: вычислительной сложности задачи.

Перемножить в уме два целых числа обычно сложнее, чем их сложить, а возвести число в степень себя (xx), как правило, вообще невозможно без вычислительной техники.

Определим вычислительную сложность более формально. Сразу условимся, что в данном случае нас интересуют не индивидуальные, а массовые задачи, то есть параметрические семейства задач, где параметрами задачи являются исходные данные. Причем каждая индивидуальная задача имеет конечное число потенциальных ответов, каждый из которых можно проверить. Это значит, что в нашем случае вопрос о разрешимости задачи не стоит, вопрос только в трудоемкости алгоритма нахождения ответа.

Можно полагать, что входными данными алгоритма является двоичное (или десятичное, это неважно) число, состоящее из n цифр. Число операций A(n), которые выполняет алгоритм для получения ответа, тоже зависит от n.

Например, в случае алгоритма сложения на вход подаются двоичные представления двух чисел, длина которых не превосходит n. Ясно, что их сумму можно получить за линейное относительно n число операций над битами (в случае десятичной записи — операций над десятичными цифрами). Более точное определение числа операций зависит от конкретного множества используемых элементарных операций и для нас сейчас неважно. Мы будем сортировать задачи по сложности — скорости роста функции A(n) — весьма грубо: линейный (в зависимости от n) рост сложности, полиномиальный рост и рост быстрее полиномиального.

На самом деле, поскольку у нас всего 2n различных наборов входных данных, мы можем заранее выписать все возможные 2n ответов, и алгоритм будет просто перебирать ответы, чтобы найти правильный. Тогда нам понадобится не более C(n)·2n операций, где C(n) — сложность проверки правильности ответа.

Решить или проверить?

В математике (и в жизни!) часто встречаются задачи, когда найти правильный ответ нелегко, а вот проверить правильность предъявленного ответа гораздо проще. Задачи, для которых сложность проверки ответа C(n) растет не более чем полиномиально, как раз и составляют класс NP. А те задачи, для которых сложность нахождения ответа A(n) растет полиномиально, составляют класс P.

Конечно, класс P содержится в классе NP — для проверки правильности ответа мы можем просто решить задачу. В знаменитой проблеме, которую мы сейчас обсуждаем, нужно выяснить, верно ли обратное: если решение задачи можно вычислительно просто проверить, то можно ли ее вычислительно просто решить?

С точки зрения здравого смысла это сомнительно. Например, рассмотрим задачу о нахождении гамильтонова цикла в графе. Пусть задан граф на n вершинах, то есть некоторый набор вершин (точек), в котором некоторые пары вершин соединены ребрами (отрезками), а некоторые нет. Нужно выяснить, найдется ли такой циклический путь по ребрам графа, который по разу проходит через все вершины (гамильтонов цикл). Ясно, что объем перебора всевозможных путей в графе быстро растет с ростом числа вершин и ребер.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Тихоходкам набили татуировки электронным пучком Тихоходкам набили татуировки электронным пучком

Китайские материаловеды нанесли татуировки живым тихоходкам

N+1
Дача-феникс Дача-феникс

Директор школы “Детали” Татьяна Рогова отстроила новый дом после пожара

AD
На шаг ближе к колонизации: как искусственный интеллект помогает NASA изучать Марс На шаг ближе к колонизации: как искусственный интеллект помогает NASA изучать Марс

О том, как ИИ помогает исследовать Марс, и приведет ли он нас к прорыву

ТехИнсайдер
10 культовых парочек из фильмов, чьи образы стоит воплотить на Хеллоуин 10 культовых парочек из фильмов, чьи образы стоит воплотить на Хеллоуин

Культовые и незаезженные парочки, чьи образы запомнятся на любой вечеринке

Cosmopolitan
Прививка от аллергии АСИТ — как она работает? Прививка от аллергии АСИТ — как она работает?

Вместо того чтобы смягчать симптомы аллергии, можно устранить причину

СНОБ
4 странные попытки великих людей написать книги и что из этого вышло 4 странные попытки великих людей написать книги и что из этого вышло

Как исторические личности пробовали себя в писательском ремесле

Maxim
«В нашем мозгу непонятно каким образом записан весь мир» «В нашем мозгу непонятно каким образом записан весь мир»

Игорь Кричевер: мехмат ничем не отличается от творческих вузов наподобие МХАТа

Наука
Твой персональный код Твой персональный код

Какими бывают тесты ДНК

Популярная механика
10 прочнейших автомобилей, способных пересечь пустыню 10 прочнейших автомобилей, способных пересечь пустыню

Автомобили, способные пересечь пустыню не хуже тачек из «Безумного Макса»

Популярная механика
Что стало с одеждой принцессы Дианы после ее смерти и другие тайны ее гардероба Что стало с одеждой принцессы Дианы после ее смерти и другие тайны ее гардероба

Зачем одежду леди Ди сожгли после автокатастрофы, как она носила старые вещи?

Cosmopolitan
Всё просто: как цифровизация делает международную торговлю понятной и доступной Всё просто: как цифровизация делает международную торговлю понятной и доступной

Как технологии помогают бизнесу сделать международную торговлю доступной

Inc.
Кто виноват в ДТП? Видео вызвало споры в соцсетях (в ГИБДД все объяснили) Кто виноват в ДТП? Видео вызвало споры в соцсетях (в ГИБДД все объяснили)

Кто нарушил правила дорожного движения и кто виноват в этой аварии?

РБК
Философия вегетарианства: взгляд изнутри и снаружи Философия вегетарианства: взгляд изнутри и снаружи

История вегатарианки с 8-летним опытом и комментарий специалиста-диетолога

Playboy
Самые дурацкие афродизиаки в истории человечества Самые дурацкие афродизиаки в истории человечества

Дуриан, картошка, яд жабы и другие странные афродизиаки

Maxim
«Разум — наш самый мощный инструмент. Нет ничего, что он не мог бы осуществить» «Разум — наш самый мощный инструмент. Нет ничего, что он не мог бы осуществить»

Павел Дуров — о разуме, воле, свободе и корпорациях

Inc.
Как сплести кольчугу: расследование ПМ Как сплести кольчугу: расследование ПМ

Почему кольчуга была популярна там, где любая ошибка вела к смерти?

Популярная механика
Для акупунктурных точек нашли анатомическую основу и рефлекторную цепь Для акупунктурных точек нашли анатомическую основу и рефлекторную цепь

Идея иглоукалывания объясняется учеными

N+1
Почувствуй себя старым: Интернету — 52 года Почувствуй себя старым: Интернету — 52 года

Каким выглядел первый сайт, первый интернет-магазин и был ли Интернет в СССР?

Maxim
Талисман: как правильно выбрать камень, который принесет тебе удачу? Талисман: как правильно выбрать камень, который принесет тебе удачу?

Как выбрать камень, который подойдет именно тебе?

Cosmopolitan
Все в наших руках Все в наших руках

Здоровье наших подруг и жен в прямом смысле в наших руках

Men’s Health
Черви-мусороеды, солнце в банке, съедобные бутылки: 5 значимых экоразработок последних 10 лет Черви-мусороеды, солнце в банке, съедобные бутылки: 5 значимых экоразработок последних 10 лет

5 экологических разработок, которые способны изменить жизнь на планете

Популярная механика
Клеймо «плюс-сайз». Что не так с появлением Джилл Кортлев на обложке российского Vogue Клеймо «плюс-сайз». Что не так с появлением Джилл Кортлев на обложке российского Vogue

В таком контексте дискурс о бодипозитиве выглядит очередным глянцевым лицемерием

СНОБ
Кубик и Рубик. Сравнится ли Duster с Jimny на офф-роуде? Кубик и Рубик. Сравнится ли Duster с Jimny на офф-роуде?

Сравнение Renault Duster с Suzuki Jimny на первый взгляд выглядит нелогичным

4x4 Club
«Синдром старшей сестры»: почему он возникает и как влияет на наше будущее «Синдром старшей сестры»: почему он возникает и как влияет на наше будущее

Рассказываем об истоках «синдрома старшей сестры» и возможных его последствиях

Psychologies
«ЖЖ — всего лишь транспорт, который устарел». Медиаменеджер Демьян Кудрявцев — об интернете нулевых и его главных действующих лицах «ЖЖ — всего лишь транспорт, который устарел». Медиаменеджер Демьян Кудрявцев — об интернете нулевых и его главных действующих лицах

Демьян Кудрявцев о былом интернете, цензуре и о том, почему ЖЖ в России взлетел

Esquire
«Я сходила с ума». Мать заработала острый психоз из-за послеродовой депрессии «Я сходила с ума». Мать заработала острый психоз из-за послеродовой депрессии

Кэтрин Шоу из Шрусбери, Великобритания, родила Джуд в разгар пандемии

Cosmopolitan
«Били линейкой по рукам»: как обучение превращается в мучение «Били линейкой по рукам»: как обучение превращается в мучение

Что делать, если учителя издеваются над детьми?

Psychologies
Делай раз, делай два: какие продукты рекомендуются по группе крови Делай раз, делай два: какие продукты рекомендуются по группе крови

От группы крови зависит, какие продукты идут тебе на пользу, а какие — нет

VOICE
Исследование: 60% россиянок считают, что расходы на беременность — забота мужчины Исследование: 60% россиянок считают, что расходы на беременность — забота мужчины

Россиянки считают, что отец должен взять на себя расходы на беременность

Forbes
Жена поспорила с мужем и перестала убирать в доме – вот что из этого вышло Жена поспорила с мужем и перестала убирать в доме – вот что из этого вышло

Что делать, если кто-то уверен, что всё домашнее хозяйство держится на нем?

Cosmopolitan
Открыть в приложении