Рассказываем о неравенстве 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
В старой коллекции находок из Костёнок нашли три кроманьонских зуба В старой коллекции находок из Костёнок нашли три кроманьонских зуба

Ученые обнаружили три кроманьонских человеческих зуба в Костёнки-1

N+1
Как понять, что вы относитесь к жизни слишком серьезно Как понять, что вы относитесь к жизни слишком серьезно

Как понять, что вы тот самый человек, которому не хватает легкости?

Psychologies
Шаги на чердаке: жуткая история о нераскрытом убийстве в Хинтеркайфеке Шаги на чердаке: жуткая история о нераскрытом убийстве в Хинтеркайфеке

Более 100 лет назад на ферме Андреаса Грубера произошла страшная трагедия

ТехИнсайдер
Почему мужчины любят стерв? Почему мужчины любят стерв?

Можно ли построить крепкие отношения со стервой?

Psychologies
Тимоти Шаламе Тимоти Шаламе

Правила жизни актера Тимоти Шаламе

Esquire
«Прощай, сестра»: история одного семейного крушения «Прощай, сестра»: история одного семейного крушения

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

Psychologies
Вкусно, полезно, доступно: 5 сезонных продуктов для тех, кто хочет похудеть Вкусно, полезно, доступно: 5 сезонных продуктов для тех, кто хочет похудеть

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

VOICE
Дина Рубина: В благодетельных дебрях психиатрии. Отрывок из романа «Маньяк Гуревич» Дина Рубина: В благодетельных дебрях психиатрии. Отрывок из романа «Маньяк Гуревич»

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

СНОБ
Раскрыты характеристики российской многоразовой ракеты с поворотным крылом Раскрыты характеристики российской многоразовой ракеты с поворотным крылом

Российские специалисты рассказали о характеристиках ракеты-носителя «Иркут»

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

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

Наука
Марина Казанкова: Марина Казанкова:

Интервью с актрисой Мариной Казанковой

Караван историй
Как утопия превратилась в фэнтези Как утопия превратилась в фэнтези

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

Weekend
9 способов снять эмоциональное напряжение 9 способов снять эмоциональное напряжение

Подавленные эмоции бьют по здоровью и отношениям с близкими

Cosmopolitan
«Вы не сможете остановить освобождение женщин»: история первой исламской феминистки «Вы не сможете остановить освобождение женщин»: история первой исламской феминистки

Фатиме Заррин-Тадж Барагани Казвини — поэтесса, активистка, феминистка из Ирана

Forbes
Они идут Они идут

Часы сегодня — средство самовыражения и туристический аттракцион

Вокруг света
Черный углерод в ледяных кернах указал на время прибытия маори в Новую Зеландию Черный углерод в ледяных кернах указал на время прибытия маори в Новую Зеландию

Около 1297 года произошел резкий рост выбросов черного углерода

N+1
Странные и смешные тени, сфотографированные при обычных обстоятельствах (галерея) Странные и смешные тени, сфотографированные при обычных обстоятельствах (галерея)

Авторам этих фотографий попалось, действительно, нечто особенное!

Maxim
Где восторг? Почему полет Пересильд в космос не взволновал россиян Где восторг? Почему полет Пересильд в космос не взволновал россиян

Вместе с открытием космоса придется перепридумать и язык человеческих эмоций

СНОБ
«Я встречаюсь с двумя мужчинами, и мне это нравится» «Я встречаюсь с двумя мужчинами, и мне это нравится»

Чем так привлекательны полигамные отношения?

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

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

Forbes
Правило № 67: Не играйте на путях Правило № 67: Не играйте на путях

Коуч Алексей Ситников исполняет свою версию арии «Что наша жизнь? Игра!»

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

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

N+1
«Чем хлеб белее, тем умрешь скорее»: навигатор еды от диетолога Майкла Поллана «Чем хлеб белее, тем умрешь скорее»: навигатор еды от диетолога Майкла Поллана

Книга диетолога Майкла Поллана — отличный навигатор по разумному питанию

Forbes
Вино по новым правилам Вино по новым правилам

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

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

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

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

Ученые исследовали артефакт возрастом около тысячи лет, обнаруженный в Перу

N+1
Своя морковка круглый год Своя морковка круглый год

Сеем морковку под зиму

Наука и жизнь
Незапрещенная профессия Незапрещенная профессия

Как женщины уже 20 лет руководят российской журналистикой

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