Рассказываем о неравенстве 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
Дети, разводы и лишние килограммы: легендарные «Друзья» 27 лет спустя Дети, разводы и лишние килограммы: легендарные «Друзья» 27 лет спустя

Как выглядят и чем живут актеры «Друзей»?

Cosmopolitan
Генетики прочитали ДНК последних охотников-собирателей Гималаев Генетики прочитали ДНК последних охотников-собирателей Гималаев

Генетики проанализировали ДНК больше ста представителей группы рауте

N+1
Убить прокрастинатора: 5 книг о привычках, которые изменят вашу жизнь Убить прокрастинатора: 5 книг о привычках, которые изменят вашу жизнь

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

Популярная механика
Совет от ученых, как есть достаточно белка, если отказаться от яиц Совет от ученых, как есть достаточно белка, если отказаться от яиц

Какие альтернативные варианты белка стоит добавить в свой рацион?

ТехИнсайдер
Непоследняя девушка: как новые слешеры переосмысляют классический образ жертвы Непоследняя девушка: как новые слешеры переосмысляют классический образ жертвы

Как теперь сценаристы обращаются с выжившими персонажами хорроров

Esquire
Книги, которые изменят вас в лучшую сторону Книги, которые изменят вас в лучшую сторону

Эти книги заставляют посмотреть на жизнь иначе, заново понять, кто такой лидер

Популярная механика
Редкого полосатого филина впервые сфотографировали в дикой природе Редкого полосатого филина впервые сфотографировали в дикой природе

Этот вид был открыт в 1872 году, но с тех пор редко попадался на глаза ученым

N+1
ПМС: болезнь или каприз ПМС: болезнь или каприз

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

Лиза
Почему в день рождения принято есть торт Почему в день рождения принято есть торт

Как торт со свечами на день рождения стал неотъемлемой частью культуры

Популярная механика
Самые большие заблуждения о психологах Самые большие заблуждения о психологах

Психологи — обычные люди со своими проблемами и радостями

Psychologies
После премьеры «Вечных» эксперт рассказал, как менялось лицо Анджелины Джоли После премьеры «Вечных» эксперт рассказал, как менялось лицо Анджелины Джоли

Как менялось лицо Анджелины Джоли

Cosmopolitan
Советская автомобильная иллюстрация: 1976 год Советская автомобильная иллюстрация: 1976 год

Необычная автомобильная подборка – из набора карманных календариков 1976 года

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

Что такое моделинг в Китае

Vogue
Генерал-рекетмейстер Генерал-рекетмейстер

Единственный портрет Боровиковского, разгадка которого заняла более полувека

Дилетант
Города, ушедшие под воду Города, ушедшие под воду

Эти "Атлантиды" тысячелетиями ждут своего часа, чтобы их исследовали

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

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

N+1
Стрекозы преодолели Индийский океан благодаря попутным ветрам Стрекозы преодолели Индийский океан благодаря попутным ветрам

Рыжие бродяжки мигрируют без остановок более чем на 2000 километров

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

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

Cosmopolitan
Неоклассика в жемчужных тонах Неоклассика в жемчужных тонах

Элегантный интерьер на все времена

SALON-Interior
«Я попросил девушку есть меньше, и она перестала со мной разговаривать» «Я попросил девушку есть меньше, и она перестала со мной разговаривать»

У автора истории оказались веские причины для ограничения. Кто же из них прав?

Psychologies
Ленин — гриб Ленин — гриб

Как появилась теория о том, что Владимир Ленин — гриб

Собака.ru
Дамблдор от моды. Парижский показ-трибьют Альберу Эльбазу, который войдет в историю Дамблдор от моды. Парижский показ-трибьют Альберу Эльбазу, который войдет в историю

Шоу-трибьют в честь Альбера Эльбаза

Esquire
Незолотое кольцо: 5 лучших архитектурных маршрутов по России Незолотое кольцо: 5 лучших архитектурных маршрутов по России

У нас огромное количество памятников разнообразных архитектурных стилей

Популярная механика
Не форсировать события и не тратить деньги на рекламу: как развивается автопереключатель раскладки Caramba Switcher Не форсировать события и не тратить деньги на рекламу: как развивается автопереключатель раскладки Caramba Switcher

Интервью с создателем Caramba Switcher Сергеем Москалёвым

VC.RU
6 фильмов ужасов, основанных на реальных событиях 6 фильмов ужасов, основанных на реальных событиях

К сожалению, страшные истории случаются не только в фильмах

Playboy
Не врать, не прокрастинировать и не сдаваться: Пол Грэм о правилах усердного труда Не врать, не прокрастинировать и не сдаваться: Пол Грэм о правилах усердного труда

Пол Грэм: действительно ли успех невозможен без упорного труда?

Forbes
Победили в Победили в

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

Cosmopolitan
Как правильно хранить резину: с дисками и без (важная инструкция) Как правильно хранить резину: с дисками и без (важная инструкция)

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

РБК
«Что мне помогло победить панические атаки» «Что мне помогло победить панические атаки»

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

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