Рассказываем о неравенстве 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 вершинах, то есть некоторый набор вершин (точек), в котором некоторые пары вершин соединены ребрами (отрезками), а некоторые нет. Нужно выяснить, найдется ли такой циклический путь по ребрам графа, который по разу проходит через все вершины (гамильтонов цикл). Ясно, что объем перебора всевозможных путей в графе быстро растет с ростом числа вершин и ребер.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

1647-летний можжевельник из Финляндии назвали старейшим древесным растением тундры и Европы 1647-летний можжевельник из Финляндии назвали старейшим древесным растением тундры и Европы

Старейший можжевельник из Финляндии рос с 260 по 1906 год

N+1
20 ошибок, которые совершает почти каждый владелец кошки 20 ошибок, которые совершает почти каждый владелец кошки

Иногда наша любовь может навредить кошке.

Популярная механика
Теория крохотных черных дыр Стивена Хокинга, нашла подтверждение на дне моря Теория крохотных черных дыр Стивена Хокинга, нашла подтверждение на дне моря

Ученые, кажется, нашли крошечную черную дыру, о которой писал Стивен Хокинг

ТехИнсайдер
Как живут люди с расстройством пищевого поведения Как живут люди с расстройством пищевого поведения

О причинах развития булимии, ее симптомах и о том, как помочь

GQ
Используй ложку и телефон: 20 способов доставить себе удовольствие Используй ложку и телефон: 20 способов доставить себе удовольствие

Двадцать разных способов мастурбации на любой вкус и цвет

Cosmopolitan
Раскрыты характеристики российской многоразовой ракеты с поворотным крылом Раскрыты характеристики российской многоразовой ракеты с поворотным крылом

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

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

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

N+1
Блогерский счет: как бум частных инвесторов изменил жизнь финансовых инфлюенсеров Блогерский счет: как бум частных инвесторов изменил жизнь финансовых инфлюенсеров

Что изменилось в работе блогеров вместе с бумом частных инвесторов?

Forbes
5 сериалов, которые помогут перенести новый локдаун 5 сериалов, которые помогут перенести новый локдаун

Несколько сериалов, остановиться смотреть которые практически невозможно.

GQ
Загадки психосоматики Загадки психосоматики

Частые или длительные стрессы ведут к развитию заболеваний – это известный факт

Лиза
Как правильно носить черное: 9 способов не стать мрачной и безликой Как правильно носить черное: 9 способов не стать мрачной и безликой

Если в твоем гардеробе преобладает черная одежда, скорее читай инструкцию

Cosmopolitan
Зачарованная война Зачарованная война

О «Повести пламенных лет» Юлии Солнцевой, получившей приз за режиссуру в Канне

Weekend
5 способов сделать жизнь дома комфортнее 5 способов сделать жизнь дома комфортнее

Умный дом, светодизайн, VR и другие способы сделать дом лучше

Популярная механика
Гаджеты из прошлого: топ-6 крутых устройств, вызывающих прилив ностальгии Гаджеты из прошлого: топ-6 крутых устройств, вызывающих прилив ностальгии

Гаджеты, которые оставались в тренде годами, если не десятилетиями

CHIP
Стриминг. Онлайн-кинотеатр Стриминг. Онлайн-кинотеатр

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

Esquire
Как психологи справляются с утренним стрессом: 8 способов Как психологи справляются с утренним стрессом: 8 способов

Что делать, если вы проснулись с плохим настроением?

Psychologies
Песчаные дюны оказались способны образовывать пары на расстоянии Песчаные дюны оказались способны образовывать пары на расстоянии

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

N+1
Неудачные свидания после знакомства в интернете: 5 историй Неудачные свидания после знакомства в интернете: 5 историй

Кому-то удается найти себе пару через приложения, но точно не нашим героям

Psychologies
Золотая лихорадка Золотая лихорадка

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

Vogue
4 неожиданных способа добычи золота 4 неожиданных способа добычи золота

Вокруг нас, оказывается, раскидана уйма золота

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

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

Лиза
«Она постоянно растет и мешает мне жить». Женщина пожаловалась на большую грудь «Она постоянно растет и мешает мне жить». Женщина пожаловалась на большую грудь

Мелисса-Мэй Лита стала недовольна рекордно большим бюстом

Cosmopolitan
Как распознать в будущем муже склонность к алкоголизму Как распознать в будущем муже склонность к алкоголизму

Как распознать в мужчине-романтике служителя «зеленого змия»

Psychologies
Секс и саспенс в Белграде Секс и саспенс в Белграде

«Дунай» Любови Мульменко, поляроидный снимок докарантинной эпохи

Weekend
Маньяки в наушниках: 9 самых интересных подкастов о реальных преступлениях Маньяки в наушниках: 9 самых интересных подкастов о реальных преступлениях

Как развивался жанр true crime

Forbes
Секс, ложь, насилие. Темная сторона секса Секс, ложь, насилие. Темная сторона секса

Что заставляет людей переходить на сторону зла и как приручить демонов?

СНОБ
Честно о раке груди Честно о раке груди

Вокруг рака молочной железы по-прежнему много слухов и домыслов

Cosmopolitan
Театральный продюсер Евгения Шерменева о творчестве в пандемию и театре в инстаграме Театральный продюсер Евгения Шерменева о творчестве в пандемию и театре в инстаграме

Театральный продюсер Евгения Шерменева — о театре, видео и дискретности времени

СНОБ
«У нас были итальянские разборки»: Бондаренко раскрыл причину развода с актрисой «У нас были итальянские разборки»: Бондаренко раскрыл причину развода с актрисой

Станислав Бондаренко высказался об отношениях с экс-избранницей Юлией Чиплиевой

Cosmopolitan
Кто изобрел аэрозольный баллончик? Кто изобрел аэрозольный баллончик?

Первый шаг к применению аэрозольных баллонов сделал изобретатель Эрик Ротхейм

Популярная механика
Открыть в приложении