Рассказываем о неравенстве 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
Вперед, к моногамии: как предотвратить измену Вперед, к моногамии: как предотвратить измену

Измена входит в топ-3 причин развода. Но можно ли ее избежать?

Cosmopolitan
Австралийские птицы отличились несоответствием между генетическим и фенотипическим полом Австралийские птицы отличились несоответствием между генетическим и фенотипическим полом

Реверсия пола наблюдалась почти у пяти процентов особей австралийских птиц

N+1
Аэродинамика скоростных поездов: почему ветер не мешает TGV Аэродинамика скоростных поездов: почему ветер не мешает TGV

Поезд TGV Париж – Нант отходит от парижского вокзала Монпарнас почти бесшумно

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

Что такое синдром Стендаля и в чем он выражается

ТехИнсайдер
6 способов стать лучше, но остаться самим собой 6 способов стать лучше, но остаться самим собой

Как можно изменить свою жизнь, не стараясь стать кем-то другим

Psychologies
Свет сошелся Свет сошелся

Chanel: практическая магия Коко и сюрреалистические киноэксперименты Кокто

Harper's Bazaar
Чертова Золушка. Чем плохи сказки, на которых мы выросли Чертова Золушка. Чем плохи сказки, на которых мы выросли

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

СНОБ
Почему возникает депрессия и как ее лечить Почему возникает депрессия и как ее лечить

Что на самом деле поможет справиться с депрессией?

РБК
Найден способ повысить износостойкость стали в агрессивной среде Найден способ повысить износостойкость стали в агрессивной среде

Покрытие может существенно повысить защиту морской и прибрежной инфраструктуры

Популярная механика
Они нам правда нравились? Красавчики из латиноамериканских сериалов Они нам правда нравились? Красавчики из латиноамериканских сериалов

Когда-то постеры с их лицами висели у нас над кроватью

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

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

Esquire
Наталья Петрова: «Пионеры Русской Америки» Наталья Петрова: «Пионеры Русской Америки»

Книга Натальи Петровой о тех, кто оставил значительный след в истории Аляски

СНОБ
Читать нельзя бросить: 6 сложных фантастов, которые смогут вас удивить Читать нельзя бросить: 6 сложных фантастов, которые смогут вас удивить

Поверьте, игра стоит свеч – не зря же эти книги стали фантастической классикой!

Популярная механика
Себя не помня: 10 знаменитостей с деменцией Себя не помня: 10 знаменитостей с деменцией

Что объединяет Уинстона Черчилля, Робина Уильямса и Маргарет Тэтчер?

Cosmopolitan
Наладили производство подделок и обманули Лувр: как братья из Одессы заработали на фальшивых древностях Наладили производство подделок и обманули Лувр: как братья из Одессы заработали на фальшивых древностях

Купцы из Одессы продали Франции подделку под видом древней золотой тиары

VC.RU
Даосские женские практики для интимных мышц Даосские женские практики для интимных мышц

Даосская практика с нефритовым яйцом — кому она может быть полезна?

Psychologies
Водителям выдают квадратные номера: зачем нужны и как получить Водителям выдают квадратные номера: зачем нужны и как получить

Что за квадратные номера и кто может их получить

РБК
Не мешай: что важно знать о совместимости продуктов и диете раздельного питания Не мешай: что важно знать о совместимости продуктов и диете раздельного питания

О диете раздельного питания, которая помогает сбросить вес.

Cosmopolitan
Глория Свенсон VS Белла Хадид: как менялись женские стандарты красоты за 100 лет Глория Свенсон VS Белла Хадид: как менялись женские стандарты красоты за 100 лет

Как изменились идеалы красоты со времен золотого века Голливуда?

Cosmopolitan
Всеобщий друг, интеллектуал и провокатор. Каким был Антон Носик Всеобщий друг, интеллектуал и провокатор. Каким был Антон Носик

Без Антона Носика не было бы не только русской блогосферы

Esquire
Счастье — есть: 6 групп продуктов, которые быстро поднимут тебе настроение Счастье — есть: 6 групп продуктов, которые быстро поднимут тебе настроение

Список полезных и при этом улучшающих самочувствие и тонус продуктов

Лиза
Преждевременно побелевшие канадские зайцы не стали легкой добычей для хищников Преждевременно побелевшие канадские зайцы не стали легкой добычей для хищников

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

N+1
На чем свет стоит На чем свет стоит

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

Tatler
Расстрел отца, ссылка матери и голод: страшное детство великой Майи Плисецкой Расстрел отца, ссылка матери и голод: страшное детство великой Майи Плисецкой

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

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

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

Esquire
Для полного счастья Для полного счастья

Все ли тренинги и марафоны от инстаграм-гуру одинаково полезны

Glamour
Как таланты раз за разом изобретали швейную машинку Как таланты раз за разом изобретали швейную машинку

Как изобрели швейную машину

Популярная механика
Писательница Алка Джоши: об индианках, Болливудских фильмах и Риз Уизерспун Писательница Алка Джоши: об индианках, Болливудских фильмах и Риз Уизерспун

Автор «Художницы из Джайпура» о том, как писала свой первый роман

Cosmopolitan
«Шесть невозможностей: Загадки квантового мира» «Шесть невозможностей: Загадки квантового мира»

Отрывок из книги Джона Гриббина — как ученые объясняют события в квантовом мире

N+1
Открыть в приложении