Рассказываем о неравенстве 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
Слишком поздно: адвокат по разводам рассказал о признаках скорого разрыва Слишком поздно: адвокат по разводам рассказал о признаках скорого разрыва

Какие красные флажки предшествуют разрыву

Cosmopolitan
У бонобо нашли вокальные диалекты У бонобо нашли вокальные диалекты

Ученые сравнили вокализации бонобо из трех разных зоопарков

N+1
Не заметить сложно: 6 очевидных признаков, что у тебя язва желудка Не заметить сложно: 6 очевидных признаков, что у тебя язва желудка

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

Cosmopolitan
Ирландская загадочность, стиль и бездонные голубые глаза: 7 лучших фильмов с Киллианом Мерфи Ирландская загадочность, стиль и бездонные голубые глаза: 7 лучших фильмов с Киллианом Мерфи

Самые знаковые работы харизматичного актера Киллиана Мерфи

Psychologies
Как долго кот помнит старого хозяина? Как долго кот помнит старого хозяина?

Вспомнит ли тебя питомец, если ты уедешь на полгода? А если на год?

Maxim
Opel Crossland для России: 5 неудобных вопросов к кроссоверу Opel Crossland для России: 5 неудобных вопросов к кроссоверу

Действительно ли это новый Opel и с кем он конкурирует

РБК
Битва при Павии. Бой времён Битва при Павии. Бой времён

Историки называют битву при Павии последней баталией Средних веков

Дилетант
Спасите ваши уши: как наушники- Спасите ваши уши: как наушники-

Ученые увидели угрозу для здоровья в беспроводных наушниках

Playboy
Это был несчастный случай: почему съемки фильмов нередко сопровождаются травмами, ( иногда — несовместимыми с жизнью) Это был несчастный случай: почему съемки фильмов нередко сопровождаются травмами, ( иногда — несовместимыми с жизнью)

Данил Леховицер вспоминает несчастные случаи на съемочных площадках

Esquire
20 самых опасных мужских профессий 20 самых опасных мужских профессий

Никогда не задумывался, почему девушек тянет к пожарным или бандитам?

Maxim
Достоверность существования стерильных нейтрино увеличили на порядок Достоверность существования стерильных нейтрино увеличили на порядок

Результаты поиска осцилляций между электронными и стерильными нейтрино

N+1
«Терпят измены, лишь бы не работать»: экс-муж Полины Гагариной осудил содержанок «Терпят измены, лишь бы не работать»: экс-муж Полины Гагариной осудил содержанок

Дмитрий Исхаков высказался о взаимоотношениях женщин и мужчин

Cosmopolitan
Советская ведьма: как графиня Мария Капнист после ГУЛАГа сделала карьеру в кино Советская ведьма: как графиня Мария Капнист после ГУЛАГа сделала карьеру в кино

Она видела, как убивали ее родственников, прошла ГУЛАГ и стала знаменита

Cosmopolitan
Телеканал, одежда, алкоголь и поддержка малого бизнеса: музыка подарила Пи Дидди славу, а предпринимательство — деньги Телеканал, одежда, алкоголь и поддержка малого бизнеса: музыка подарила Пи Дидди славу, а предпринимательство — деньги

Рэпер Шон Комбс помогает малому бизнесу и инвестирует в техпроекты

VC.RU
Как изменился секс за последние годы? Как изменился секс за последние годы?

В чем заключается особенность секса в наши дни?

Psychologies
«Иван Грозный» Сергея Эйзенштейна: фильм о Сталине или автопортрет режиссера? «Иван Грозный» Сергея Эйзенштейна: фильм о Сталине или автопортрет режиссера?

О наследии картины «Иван Грозный» Эйзенштейна, о том, как она смотрится сегодня

Esquire
«Оставила пуповину вместе с плацентой». Женщина рассказала про лотосовые роды «Оставила пуповину вместе с плацентой». Женщина рассказала про лотосовые роды

Лотосовые роды — это необычная традиция родом с Бали

Cosmopolitan
«Домашнее насилие и я: история Мии». Мия Бордман сняла фильм о бытовой тирании «Домашнее насилие и я: история Мии». Мия Бордман сняла фильм о бытовой тирании

Звезда телешоу «Teen Mom UK» сняла документальный фильм о домашнем насилии

Cosmopolitan
OLED-экран в смартфоне: почему это не всегда хорошо OLED-экран в смартфоне: почему это не всегда хорошо

OLED-дисплеи тоже имеют недостатки

CHIP
10 быстрых фактов о ленивцах 10 быстрых фактов о ленивцах

Оказывается, ленивцы умеют удивлять!

Maxim
5 небанальных фильмов на Хеллоуин 5 небанальных фильмов на Хеллоуин

Фильмы для тех, кто наизусть знает классику ужасов

GQ
Как отучить себя перерабатывать Как отучить себя перерабатывать

Советы для хронических трудоголиков

GQ
Одна вокруг света: преграды на пути в Колумбию и жизнь на яхте Одна вокруг света: преграды на пути в Колумбию и жизнь на яхте

142-я серия о кругосветном путешествии москвички Ирины Сидоренко

Forbes
Настройка экранного времени Настройка экранного времени

Интервью с телеведущим Азаматом Мусагалиевым

Glamour
Детские лагеря для взрослых: как они работают Детские лагеря для взрослых: как они работают

Как формат детского лагеря помогает современным взрослым восстановить силы

СНОБ
За пригоршню «спасибо» За пригоршню «спасибо»

Ты замечал, что бесплатно кому-то помочь бывает приятнее, чем за деньги?

Maxim
До «метавселенных» ещё далеко: три причины, почему До «метавселенных» ещё далеко: три причины, почему

Специалисты объясняют, почему «метавселенная» не так близко, как кажется

VC.RU
Древнейшим останкам из Фофановского могильника в Забайкалье оказалось 8000 лет Древнейшим останкам из Фофановского могильника в Забайкалье оказалось 8000 лет

Исследователи провели радиоуглеродный анализ находок, сделанных на Селенге

N+1
Как развивается экстремальный спорт и что ждет его в будущем Как развивается экстремальный спорт и что ждет его в будущем

Почему скейтбординг, серфинг и BMX по-прежнему остаются популярными

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