Рассказываем о неравенстве 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
9 психологических причин болезненных менструаций 9 психологических причин болезненных менструаций

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

Psychologies
Палеогенетики уточили популяционную историю Таримской впадины Палеогенетики уточили популяционную историю Таримской впадины

Как ученые анализировали геномы древних людей из Таримской впадины

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

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

Наука и жизнь
Пять языков любви Пять языков любви

Секрет прочных отношений

kiozk originals
Вредные советы для предпринимателей: как попросить денег на стартап Вредные советы для предпринимателей: как попросить денег на стартап

Прочитайте эти советы для привлечения денег в стартап и сделайте наоборот

Forbes
Несезонное предложение Несезонное предложение

Осень в Крыму создана для прогулок и гурмэ-удовольствий

Лиза
BTS BTS

Клип BTS стал абсолютным рекордом среди музыкальных видео на YouTube

ЖАРА Magazine
Укротительница тигров Маргарита Назарова: трагедия советской циркачки Укротительница тигров Маргарита Назарова: трагедия советской циркачки

Печальная история знаменитой дрессировщицы тигров

VOICE
Всё просто: как цифровизация делает международную торговлю понятной и доступной Всё просто: как цифровизация делает международную торговлю понятной и доступной

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

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

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

VC.RU
«Я попросил девушку есть меньше, и она перестала со мной разговаривать» «Я попросил девушку есть меньше, и она перестала со мной разговаривать»

У автора истории оказались веские причины для ограничения. Кто же из них прав?

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

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

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

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

Караван историй
Что помогло Юлии Пересильд стать первой в мире актрисой, полетевшей в космос Что помогло Юлии Пересильд стать первой в мире актрисой, полетевшей в космос

Актриса Юлия Пересильд и режиссер Клим Шипенко отправились в космос

Cosmopolitan
Новый главный Новый главный

Самый большой, сложный и мощный космический телескоп в истории

Популярная механика
Много получать и почти не работать — цель современной молодежи? Много получать и почти не работать — цель современной молодежи?

«Не напрягаться и получать хорошие деньги» — чего хочет подрастающее поколение?

СНОБ
Закон убывающей отдачи: как достигать успеха без лишних усилий и выгорания Закон убывающей отдачи: как достигать успеха без лишних усилий и выгорания

Как прикладывать меньше усилий и получать лучший результат

Forbes
Можно помедленнее? Можно помедленнее?

Slow sex («медленный секс»). Точно стоит попробовать, если есть время и силы

Cosmopolitan
Артем Ларин: «Игнорирование ESG может обернуться потерей рынка» Артем Ларин: «Игнорирование ESG может обернуться потерей рынка»

Что такое ESG-повестка, и как бизнесу внедрить ее в свои процессы?

РБК
Не такой, как остальные. Тест-драйв Chevrolet Trailblazer Не такой, как остальные. Тест-драйв Chevrolet Trailblazer

Где выпускают самый маленький кроссовер Chevrolet?

РБК
«Ашрам Шамбалы». Часть 3: Как сбежать из секты и устроить свою жизнь после «Ашрам Шамбалы». Часть 3: Как сбежать из секты и устроить свою жизнь после

Как удалось поймать гуру «Ашрам Шамбалы» и почему секта на этом не закончилась

СНОБ
Что такое никотиновая кислота и как ее можно использовать Что такое никотиновая кислота и как ее можно использовать

Полезные свойства никотиновой кислоты оставались недооцененными

РБК
Анастасия Вертинская: Анастасия Вертинская:

Анастасия Вертинская вспоминает свое детство и рассказывает о родителях

Караван историй
Группа ноль. Что нужно знать о самой редкой группе крови? Группа ноль. Что нужно знать о самой редкой группе крови?

Нулевой резус-фактор — самая редкая группа крови

Esquire
Молодо — зелено Молодо — зелено

Каково влияние ESG-трендов на жизнь людей сегодня и завтра

РБК
Хэллоуин по-русски: 10+ самых странных мистических историй из реальной жизни Хэллоуин по-русски: 10+ самых странных мистических историй из реальной жизни

Пугающие и смешные мистические истории

Cosmopolitan
Хорошо, как дома Хорошо, как дома

Квартира в Санкт-Петербурге вдохновленная работами американских декораторов

AD
Как в США несколько лет сражались за яйца — история одной нелепой войны Как в США несколько лет сражались за яйца — история одной нелепой войны

Война за яйца: в ходе неё гибли люди и едва ли не погибла целая экосистема

Популярная механика
Закадровые голоса Закадровые голоса

Стилисты, визажисты, стажеры рассказывают, как попасть в глянец

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