Рассказываем о неравенстве 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
Уже рядом: 5 отличных книг о будущем Уже рядом: 5 отличных книг о будущем

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

Популярная механика
Найдены жировые клетки, которые являются «пузырьковой защитой» организма Найдены жировые клетки, которые являются «пузырьковой защитой» организма

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

ТехИнсайдер
Губы ТП-69: обходи стороной мастера, который предложит тебе такое! Губы ТП-69: обходи стороной мастера, который предложит тебе такое!

В России орудует банда «черных косметологов»

Cosmopolitan
Два месяца под землей без света и общения с людьми: эксперимент Мишеля Сифра Два месяца под землей без света и общения с людьми: эксперимент Мишеля Сифра

Как проходил эксперимент Мишеля Сифра и к каким он пришел выводам

ТехИнсайдер
Косметологи-недоучки калечат женщин! Распознаем мошенников по фото в соцсетях Косметологи-недоучки калечат женщин! Распознаем мошенников по фото в соцсетях

Проблема подпольной пластической хирургии еще не близка к разрешению

Cosmopolitan
Телец - Сара Коннор, Рак - Баффи. Кем тебе нарядиться на хэллоуинскую вечеринку? Телец - Сара Коннор, Рак - Баффи. Кем тебе нарядиться на хэллоуинскую вечеринку?

Подборка идей для хэллоуинских нарядов

Cosmopolitan
Длиною в жизнь Длиною в жизнь

Жизнь человека как биологического вида конечна?

Grazia
Главные изменения в ПДД за последнее время: водители о них уже забыли Главные изменения в ПДД за последнее время: водители о них уже забыли

За последние четыре года ПДД меняли 17 ра

РБК
Как позаботиться о себе, если у тебя «работа на ногах» Как позаботиться о себе, если у тебя «работа на ногах»

Реально ли избежать постоянной усталости ног от стоячей работы?

Лиза
Гибкая личность: как избавиться от ярлыков и стать тем, кем хочешь Гибкая личность: как избавиться от ярлыков и стать тем, кем хочешь

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

РБК
Человек-оркестр Человек-оркестр

Монозадачность – это не врожденное качество, а тонкое искусство

Лиза
Последняя гастроль империи Последняя гастроль империи

Анна Толстова о самой провальной выставке русского искусства в Америке

Weekend
Как добиться лучших условий при приеме на работу Как добиться лучших условий при приеме на работу

Идете на собеседование? Подготовьтесь к переговорам

Psychologies
16 ненужных вещей, без которых ты не представляешь своей жизни 16 ненужных вещей, без которых ты не представляешь своей жизни

Вещи, которые нам совершенно не нужны, но без которых совершенно невозможно жить

Cosmopolitan
На измене. Почему супруги не хранят верность друг другу На измене. Почему супруги не хранят верность друг другу

70% людей хотя бы один раз изменяли постоянному партнеру

СНОБ
Легендарный завод ГЗСА: советские «Почта» и «Хлеб» Легендарный завод ГЗСА: советские «Почта» и «Хлеб»

Одними из самых распространённых в СССР автомобилей были ГЗСА

Популярная механика
«Это все мое, родное»: лучшая точка для отдыха в России «Это все мое, родное»: лучшая точка для отдыха в России

Fвторские программы по Северному Приладожью, которые открывают новые маршруты

Psychologies
Голос, космос и различные странности. Что все-таки нас объединяет? Голос, космос и различные странности. Что все-таки нас объединяет?

Журналист Сююмбике Давлет-Кильдеева — о громком молчании

РБК
Слова-маркеры Ксении Собчак. Что они говорят о настроениях среднего класса Слова-маркеры Ксении Собчак. Что они говорят о настроениях среднего класса

Список слов-маркеров от Ксении Собчак

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

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

РБК
7 самых необычных и таинственных мест на планете 7 самых необычных и таинственных мест на планете

Эти уголки планеты заставят вас удивиться

Playboy
«Золотая жила» неслучившейся беды: почему в команде нужно обращать внимание на катастрофы, которых не было «Золотая жила» неслучившейся беды: почему в команде нужно обращать внимание на катастрофы, которых не было

Что, если бы компании могли учиться на своих ошибках, при этом их не совершая?

VC.RU
«Дома перестанут зависеть от внешних источников энергии» «Дома перестанут зависеть от внешних источников энергии»

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

РБК
Почему неугодных русским царям жен и дочерей ссылали в монастырь? Почему неугодных русским царям жен и дочерей ссылали в монастырь?

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

Культура.РФ
10 пейзажей, которые неузнаваемо изменило время 10 пейзажей, которые неузнаваемо изменило время

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

Maxim
Дюны: наикратчайший путеводитель Дюны: наикратчайший путеводитель

Все самое главное о дюнах в реальном мире, на нашей планете и на соседних

Популярная механика
«Я влюбилась, поехала крыша!»: Галина Беседина призналась, что изменяла мужу «Я влюбилась, поехала крыша!»: Галина Беседина призналась, что изменяла мужу

Галина Беседина раскрыла причины первого развода и отсутствия детей

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

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

Наука и жизнь
Умная стрижка, с которой не нужно делать укладку: примеры для волос разной длины Умная стрижка, с которой не нужно делать укладку: примеры для волос разной длины

Умная стрижка — изобретение парикмахеров, которое всем нам просто необходимо

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