Рассказываем о неравенстве 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
61 год громкой истории про то, как Хрущев стучал ботинком по столу в ООН 61 год громкой истории про то, как Хрущев стучал ботинком по столу в ООН

История о Хрущеве с ботнком

Maxim
Ученые обнаружили древнего хищника с тремя глазами и зубастым ртом! Он жил 506 млн лет назад Ученые обнаружили древнего хищника с тремя глазами и зубастым ртом! Он жил 506 млн лет назад

В Берджесс нашли окаменелость необычного существа, жившего 506 млн лет назад

ТехИнсайдер
Место большой свободы. Марта Кетро — о том, что общего у «Живого журнала» и «квартала красных фонарей» в Гамбурге Место большой свободы. Марта Кетро — о том, что общего у «Живого журнала» и «квартала красных фонарей» в Гамбурге

Марта Кетро — как блог-платформа стала социальным лифтом для ее обитателей

Esquire
«Болезни Империи. Как пытки рабов и зверства во время войн изменили медицину» «Болезни Империи. Как пытки рабов и зверства во время войн изменили медицину»

Почему во время Крымской войны большинство солдат погибало в госпиталях

N+1
Поощряют чрезмерное потребление и получают $1 с гостя: можно ли заработать на формате «платишь и ешь сколько хочешь» Поощряют чрезмерное потребление и получают $1 с гостя: можно ли заработать на формате «платишь и ешь сколько хочешь»

Можно ли «объесть» заведение?

VC.RU
Философия вегетарианства: взгляд изнутри и снаружи Философия вегетарианства: взгляд изнутри и снаружи

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

Playboy
Читатели MAXIM рассказали, куда вложили свои ваучеры Читатели MAXIM рассказали, куда вложили свои ваучеры

29 лет назад государство в лице «Сбербанка» начало раздавать населению ваучеры

Maxim
«Давай сделаем селфи»: 15 признаков, что он в тебя влюбился «Давай сделаем селфи»: 15 признаков, что он в тебя влюбился

Как понять, что ты действительно очень много для него значишь!

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

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

Forbes
Быстрый перекус Быстрый перекус

Как сделать быстрый перекус максимально безопасным?

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

Как вовремя распознать признаки ментальных проблем у сотрудника

Inc.
«У нас есть план А, план Б и план Х» Юлия Пересильд — о съемках в космосе «У нас есть план А, план Б и план Х» Юлия Пересильд — о съемках в космосе

Юлия Пересильд рассказывает, как готовится к полету на МКС

РБК
ПМС: инструкция по выживанию для мужчин ПМС: инструкция по выживанию для мужчин

ПМС — этого врага ты должен знать в лицо

Maxim
«Что-то не так с Гэлвинами». Как одна семья помогла ученым исследовать природу шизофрении «Что-то не так с Гэлвинами». Как одна семья помогла ученым исследовать природу шизофрении

История семьи, в которой у шести детей из двенадцати диагностировали шизофрению

СНОБ
«Обязательный завтрак, вредный кофе и опасный фастфуд. Почему  почти все, что нам рассказывали о еде, неправда» «Обязательный завтрак, вредный кофе и опасный фастфуд. Почему  почти все, что нам рассказывали о еде, неправда»

Насколько популярные утверждения о еде иногда далеки от правды

N+1
Титановые ногти: новый вид маникюра, который устраняет ломкость и слоение Титановые ногти: новый вид маникюра, который устраняет ломкость и слоение

Крепкие ногти — несбыточная мечта многих девушек

Cosmopolitan
Сезонное предложение Сезонное предложение

Как скорректировать свой рацион поздней осенью

Лиза
Чем была Mail.ru Group 10-20 лет назад и к чему пришла в 2021-м Чем была Mail.ru Group 10-20 лет назад и к чему пришла в 2021-м

Как менялась Mail.ru Group. От почты до экосистемы

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

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

GQ
Куртка для героя: за что Жан-Поль Бельмондо любил французский бренд Chapal Куртка для героя: за что Жан-Поль Бельмондо любил французский бренд Chapal

За что летные куртки Chapal так любил Жан-Поль Бельмондо и так ценят гонщики

Forbes
Диабулимия: смертельное пищевое расстройство, о котором мало кто слышал Диабулимия: смертельное пищевое расстройство, о котором мало кто слышал

Диабулимия – пищевое расстройство, которое встречается у пациентов с диабетом

Cosmopolitan
Карина Андоленко. В потоке Карина Андоленко. В потоке

Карина Андоленко не боится залезть в кроличью нору и узнать что-то новое

Коллекция. Караван историй
Сбой в работе WhatsApp, Instagram и Facebook: как он на нас повлиял Сбой в работе WhatsApp, Instagram и Facebook: как он на нас повлиял

Сбой в Facebook. Многие назвали произошедшее настоящим Апокалипсисом

Psychologies
Как мир перестал слышать архитекторов Как мир перестал слышать архитекторов

Проект Григория Ревзина «Оправдание утопии». Мишель Рагон: GIAP

Weekend
Зимний дворец Зимний дворец

Исторические интерьеры и экспозиции Зимнего дворца

Культура.РФ
«Благодаря аварии я нашла свое новое призвание» «Благодаря аварии я нашла свое новое призвание»

Внезапное несчастье развернуло судьбу Нины Никифоровой

Psychologies
5 ошибок Ивана Боровикова, основателя платформы автоматизации маркетинга Mindbox 5 ошибок Ивана Боровикова, основателя платформы автоматизации маркетинга Mindbox

Основатель платформы Mindbox — о своих самых критичных ошибках

Inc.
Лекарственные травы не спасли молодую женщину в Древнем Перу Лекарственные травы не спасли молодую женщину в Древнем Перу

Древние жители Перу использовали разные травы в лекарственных целях

N+1
Адская парочка: 3 худшие пары по знаку зодиака Адская парочка: 3 худшие пары по знаку зодиака

Есть такие знаки, которые просто ну никак не могут быть вместе

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