Рассказываем о неравенстве 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
Почему не стоит покупать маленький SSD: и мы не о свободном месте Почему не стоит покупать маленький SSD: и мы не о свободном месте

Почему не стоит покупать SSD небольшого объема

CHIP
Астрономы заметили в космосе таинственную идеальную сферу Астрономы заметили в космосе таинственную идеальную сферу

Объект Телиос: совершенная сфера неизвестного происхождения

ТехИнсайдер
Есть ли польза от дронов в сельском хозяйстве Есть ли польза от дронов в сельском хозяйстве

Дроны помогают контролировать этапы роста и развития выращиваемых культур

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

Как наш мозг реагирует на виртуальное питание

Forbes
Генетики нашли трех живых родственников швейцарской мумии Генетики нашли трех живых родственников швейцарской мумии

Генетики провели анализ ДНК женщины из швейцарской церкви Барфюссер

N+1
Диета при панкреатите: что можно и нельзя есть. Советы врача Диета при панкреатите: что можно и нельзя есть. Советы врача

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

РБК
7 простых способов улучшить ваши социальные навыки 7 простых способов улучшить ваши социальные навыки

Как прокачать навыки коммуникации, чтобы «выйти в люди»

Psychologies
Им под стать? Как выглядят жены и подруги красавчиков из турецких сериалов Им под стать? Как выглядят жены и подруги красавчиков из турецких сериалов

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

VOICE
Ловушка ложной скромности: почему самореклама не ругательство, а залог успеха Ловушка ложной скромности: почему самореклама не ругательство, а залог успеха

Отрывок из книги Стефани Сворд-Уильямс «К черту скромность!»

Forbes
Археологи нашли древнего китайца с ампутированной в наказание ступней Археологи нашли древнего китайца с ампутированной в наказание ступней

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

N+1
Как меняются отношения после рождения ребенка Как меняются отношения после рождения ребенка

Как победить кризис в отношениях после рождения ребенка?

Лиза
Как правильно закаляться и не замерзнуть Как правильно закаляться и не замерзнуть

Несколько полезных советов перед холодами

GQ
Только в противогазе и перчатках: как готовят самый острый соус в мире Только в противогазе и перчатках: как готовят самый острый соус в мире

Приправа, набравшая 12 миллионов единиц по шкале жгучести Сковилла

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

Самые известные чемпионки по бодибилдингу

VOICE
Прослыли предателями, но заложили дух Кремниевой долины и запустили крупнейшие техфирмы: история «вероломной восьмерки» Прослыли предателями, но заложили дух Кремниевой долины и запустили крупнейшие техфирмы: история «вероломной восьмерки»

Заимствование методов и навыков, а также жёсткая конкуренция

VC.RU
Всё время голоден: 7 причин, по которым ты постоянно хочешь есть Всё время голоден: 7 причин, по которым ты постоянно хочешь есть

Почему я всё время хочу есть?

Cosmopolitan
Кто, где и как делает и продает суррогатный алкоголь в России. И почему трагедия в Оренбургской области может повториться Кто, где и как делает и продает суррогатный алкоголь в России. И почему трагедия в Оренбургской области может повториться

В каких регионах могут повториться массовые отравления суррогатным алкоголем

СНОБ
Время старших Время старших

Как мы осознаем сегодня возраст? Рассуждают участницы сообщества Young Old

Домашний Очаг
«Мой 16-летний сын стал отцом-одиночкой» «Мой 16-летний сын стал отцом-одиночкой»

Незапланированная беременность юной подружки сына — страшный сон родителей!

Psychologies
Всё плохо и ничего не болит: 5 признаков проблем с печенью Всё плохо и ничего не болит: 5 признаков проблем с печенью

Признаки, которые указывают на заболевания печени

Cosmopolitan
Trashion, или Бросовая мода Trashion, или Бросовая мода

Как объединить фэшн-индустрию и переработку отходов

РБК
Антон Филипенко: «Адекватность должна быть во всем» Антон Филипенко: «Адекватность должна быть во всем»

Антон Филипенко о том, как стал актером и почему его однажды попросили уйти

Cosmopolitan
Под другим углом: как бренд Audi переосмысливает подход к кроссоверам Под другим углом: как бренд Audi переосмысливает подход к кроссоверам

На примере нового Q5 Sportback, объясняем, как кроссовер может быть не скучным

Forbes
Лучшие хорроры 2021 года Лучшие хорроры 2021 года

Список самых любопытных хорроров года 2021 года

Esquire
Я – шопоголик Я – шопоголик

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

Лиза
«Благодаря аварии я нашла свое новое призвание» «Благодаря аварии я нашла свое новое призвание»

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

Psychologies
Фредди Хаймор – о новом сезоне «Хорошего доктора», драмах про врачей и своих ролях Фредди Хаймор – о новом сезоне «Хорошего доктора», драмах про врачей и своих ролях

Фредди Хаймор о пятом сезоне «Хорошего доктора»

GQ
Малый Эрмитаж Малый Эрмитаж

Висячий сад и часы «Павлин»

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

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

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