Рассказываем о неравенстве 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
«Мама бросила меня. Но я все еще жду ее»: история отвергнутой дочери «Мама бросила меня. Но я все еще жду ее»: история отвергнутой дочери

Юлии тридцать лет, но она до сих пор ищет маму, которой она совсем не нужна

Psychologies
Ученые наконец-то поняли, почему от красного вина болит голова Ученые наконец-то поняли, почему от красного вина болит голова

Какие компоненты красного вина вызывают у нас головную боль?

ТехИнсайдер
Археологи раскопали три средневековых поселения под Муромом и Владимиром Археологи раскопали три средневековых поселения под Муромом и Владимиром

Ученым удалось обнаружить некрополи под Муромом и Владимиром

N+1
«Ах, сердце прихватило»: как отвечать на манипуляции дома и на работе, чтобы не поссориться «Ах, сердце прихватило»: как отвечать на манипуляции дома и на работе, чтобы не поссориться

Как сохранить отношения, если вами манипулируют?

Psychologies
В роли жертвы В роли жертвы

Постоянно рвешься спасать партнера, считая, что без тебя он пропадет?

Лиза
Выходи за толстого: 20 самых глупых советов наших мам и бабушек про отношения Выходи за толстого: 20 самых глупых советов наших мам и бабушек про отношения

Сеть переполнена «секретами наших бабушек», которые помогут сохранить брак

Cosmopolitan
Евгений Гришковец — о «Живом журнале», хейтерах и о том, как интернет мешает ремеслу Евгений Гришковец — о «Живом журнале», хейтерах и о том, как интернет мешает ремеслу

Евгений Гришковец — чему его научил ЖЖ?

Esquire
Как французский орнитолог стал вожаком стаи гусей и летал с ними на зимовку Как французский орнитолог стал вожаком стаи гусей и летал с ними на зимовку

Как орнитолог возглавил косяк и перелетел вместе с гусями через Балтийское море

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

Спутник Земли отдаляется от материнской планеты все дальше и дальше...

Популярная механика
Загадки психосоматики Загадки психосоматики

Частые или длительные стрессы ведут к развитию заболеваний – это известный факт

Лиза
Ножом по стеклу: почему нас бесят звуки и какие раздражают сильнее всех Ножом по стеклу: почему нас бесят звуки и какие раздражают сильнее всех

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

Cosmopolitan
Умножить на два Умножить на два

Песня «Юность» группы Dabro стала настоящим гимном нового поколения

OK!
Самые страшные вещи, которые люди видели в море Самые страшные вещи, которые люди видели в море

Отправляешься на берег моря с бархатным песочком? Не забудь электрошокер

VOICE
Дал бог зайку, но за что? Честные сериалы про материнство Дал бог зайку, но за что? Честные сериалы про материнство

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

Cosmopolitan
За что вручали: самые необычные формулировки Нобелевской премии по литературе За что вручали: самые необычные формулировки Нобелевской премии по литературе

Странные формулировки, которые объясняли награждение Нобелевский премией

GQ
Мода 2000-х: самые безумные образы российских звезд Мода 2000-х: самые безумные образы российских звезд

Эра «гламура» 2000-х захлестнула весь мир, и Россия не стала исключением

VOICE
Одна вокруг света: ремонт машины в Панаме и охота на голубых крабов Одна вокруг света: ремонт машины в Панаме и охота на голубых крабов

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

Forbes
Осенние цветники Осенние цветники

Кандидатов в позднецветущие композиции набирается немало

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

Археологи исследовали погребальную куклу таштыкской культуры

N+1
«Я вложила деньги в финансовую пирамиду» «Я вложила деньги в финансовую пирамиду»

«Я вложила деньги в финансовую пирамиду»

Cosmopolitan
Маэстро механики Маэстро механики

Самоучка-часовщик, который идет наперекор правилам и создает драконов и фей

Вокруг света
«У них лилась кровь — но кровь-то черная была» «У них лилась кровь — но кровь-то черная была»

Юрий Норштейн, Рената Литвинова и другие о самых страшных фильмах в их жизни

Weekend
Ученые выяснили, что мужчины и женщины считают изменой разные вещи Ученые выяснили, что мужчины и женщины считают изменой разные вещи

У разных полов отличаются представления о том, что такое измена

Maxim
Этика беспилотников: как нельзя кодировать мораль Этика беспилотников: как нельзя кодировать мораль

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

Популярная механика
Предсказывая будущее: что такое предиктивная аналитика и как она поможет избежать аварий и техногенных катастроф Предсказывая будущее: что такое предиктивная аналитика и как она поможет избежать аварий и техногенных катастроф

Возможно ли спрогнозировать поломку оборудования?

Популярная механика
Очки, линзы или лазерная коррекция: что выбрать? Очки, линзы или лазерная коррекция: что выбрать?

Глаза — орган крайне чувствительный, поэтому людей с идеальным зрением мало

Psychologies
Физики обнаружили аномалии в распаде ультрахолодных молекул NaK и NaRb Физики обнаружили аномалии в распаде ультрахолодных молекул NaK и NaRb

Новый эксперимент с молекулами потребует пересмотра квантово-химических моделей

N+1
Алена Бочарова Алена Бочарова

Интервью с основательницей Beat Film Festival Аленой Бочаровой

Собака.ru
«В школах должно возникать как можно больше правильных конфликтов» «В школах должно возникать как можно больше правильных конфликтов»

Детей нужно обучать разрешению конфликтов, а педагогов — умению уступать

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