Рассказываем о неравенстве 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
Мода 2000-х: самые безумные образы российских звезд Мода 2000-х: самые безумные образы российских звезд

Эра «гламура» 2000-х захлестнула весь мир, и Россия не стала исключением

VOICE
Эта компания построит грандиозное сооружение прямо на орбите — до сих пор никто такого не делал даже близко Эта компания построит грандиозное сооружение прямо на орбите — до сих пор никто такого не делал даже близко

Space Solar построит орбитальную электростанцию с использованием роботов

Inc.
Секрет — в брокколи Секрет — в брокколи

Ани Тейлор-Джой о триллере «Прошлой ночью в Сохо»

OK!
10 незаслуженно забытых сериалов ужасов 10 незаслуженно забытых сериалов ужасов

Десятка сериалов, забытых жемчужин хоррора

Maxim
«Оторви и выбрось» — самый недооцененный фильм минувшего «Кинотавра». Это надо срочно исправить «Оторви и выбрось» — самый недооцененный фильм минувшего «Кинотавра». Это надо срочно исправить

Очень важно не пропустить вторую картину Кирилла Соколова — «Оторви и выбрось»

Esquire
Абонент временно недоступен Абонент временно недоступен

Гаджеты тоже нужно «употреблять» дозированно

GQ
Темные светила: коричневые карлики Темные светила: коричневые карлики

Коричневые карлики – космические тела, светящие совсем недолго

Популярная механика
Откуда родом лягушка — подскажет её кожный секрет Откуда родом лягушка — подскажет её кожный секрет

Исследователи нашли новый способ различать виды и популяции лягушек

Наука и жизнь
Изменение климата повысило риск красных приливов в Чукотском море Изменение климата повысило риск красных приливов в Чукотском море

Виновники красных приливов, оказались широко распространены в Чукотском море

N+1
10 культовых парочек из фильмов, чьи образы стоит воплотить на Хеллоуин 10 культовых парочек из фильмов, чьи образы стоит воплотить на Хеллоуин

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

Cosmopolitan
Подвиг офицера, который пожертвовал собой, чтобы спасти заложников во время «Норд-Оста» Подвиг офицера, который пожертвовал собой, чтобы спасти заложников во время «Норд-Оста»

Офицер предложил террористам себя в обмен на заложников в «Норд-Осте»

Maxim
Правда и мифы о мигрени Правда и мифы о мигрени

С мигренью связано много мифов и заблуждений

Лиза
«‎Невозможно создавать микросхемы без машин ASML»‎: голландская компания, от которой зависят Apple, Samsung и Intel «‎Невозможно создавать микросхемы без машин ASML»‎: голландская компания, от которой зависят Apple, Samsung и Intel

ASML: монополист в области фотолитографии в глубоком ультрафиолете

VC.RU
Диетолог из Гарварда назвала 5 продуктов, которые помогут улучшить работу мозга и замедлить старение Диетолог из Гарварда назвала 5 продуктов, которые помогут улучшить работу мозга и замедлить старение

Ума Найду рассказала, что она ест для улучшения памяти и концентрации внимания

Inc.
Амур де труа: твой гид по сексу втроем Амур де труа: твой гид по сексу втроем

Как найти недостающее звено и подготовиться к сексу с третьим не лишним

Playboy
Состав косметики: на что обращать внимание при выборе Состав косметики: на что обращать внимание при выборе

Каждый потребитель косметических средств хотя бы раз ошибался при выборе

РБК
Не Настя, а Амина: Решетова и другие звезды, которые сменили имена Не Настя, а Амина: Решетова и другие звезды, которые сменили имена

10 примеров, когда знаменитости меняли имена

Cosmopolitan
Победа Ливерпуля Победа Ливерпуля

Как актриса Джоди Комер добилась успеха

Glamour
Мать оставила дочери шрамы на всю жизнь, пытаясь вылечить педикулез керосином Мать оставила дочери шрамы на всю жизнь, пытаясь вылечить педикулез керосином

Чарити Саттер почти 20 лет страдает от последствий лечения керосином

Cosmopolitan
Жить стало лучше: почему некоторым афганцам нравится власть талибов Жить стало лучше: почему некоторым афганцам нравится власть талибов

Находятся и те, кому происходящее в Афганистане приходится очень даже по душе

Maxim
Игорь Саруханов: Игорь Саруханов:

Интервью с певцом и композитором Игорем Сарухановым

Караван историй
Полторы минуты славы Полторы минуты славы

Продюсер звезд российского TikTok рассуждает о будущем молодых инфлюенсеров

Esquire
Скрытые сокровища Netflix: сериалы, которые ты могла пропустить (а зря!) Скрытые сокровища Netflix: сериалы, которые ты могла пропустить (а зря!)

Есть сериалы, которые у всех на слуху, а есть те, о которых почти никто не знает

Cosmopolitan
Дойти до точки Дойти до точки

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

Лиза
6 токсичных представлений о любви 6 токсичных представлений о любви

Влюбившись, мы ждем, что любовь станет ответом на все вопросы

Psychologies
Мор, труп, май Мор, труп, май

Игорь Гулин о переиздании «Мрака твоих глаз» Ильи Масодова

Weekend
Другой берег Другой берег

Черногория готова принимать гостей как с моря, так и с суши

Robb Report
Софья, Исанна Софья, Исанна

Психолог из Петербурга Исанна Аксютова придумала экобренд «ЛюбЛён»

Собака.ru
5 признаков эмоционально незрелого человека 5 признаков эмоционально незрелого человека

У вас возникает чувство, что партнер часто ведет себя как ребенок?

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