Рассказываем о неравенстве 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
Юрий Каспарян Юрий Каспарян

Солист группы «Кино» Юрий Каспарян — о прошлом и настоящем группы

Maxim
«Музей языков: Конрад Гесснер и книги-полиглоты XVI века» «Музей языков: Конрад Гесснер и книги-полиглоты XVI века»

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

N+1
Неправильный номер и собака на дороге: две истории удивительного знакомства Неправильный номер и собака на дороге: две истории удивительного знакомства

Как отступить от стереотипов общения и сделать шаг навстречу незнакомцу?

Psychologies
Индивидуалистка из СССР: как Айн Рэнд боролась с коммунизмом и создавала бестселлеры Индивидуалистка из СССР: как Айн Рэнд боролась с коммунизмом и создавала бестселлеры

Как Айн Рэнд, дочь аптекаря из Петербурга, смогла покорить США

Forbes
10 самых лучших мужских фильмов-комиксов 10 самых лучших мужских фильмов-комиксов

Суперчитатели MAXIM проголосовали за супергероя, и им суперстал…

Maxim
Никита Кукушкин. Актер нового типа Никита Кукушкин. Актер нового типа

Никита Кукушкин: «Сейчас у меня замечательное время. Я собираю камни»

Коллекция. Караван историй
Вкусная осень Вкусная осень

В топе самых полезных осенних фруктов – гранат, хурма и грейпфрут!

Добрые советы
Цифровая смерть: о чем стоит подумать пользователям соцсетей после сбоя Facebook Цифровая смерть: о чем стоит подумать пользователям соцсетей после сбоя Facebook

Привычные нам сервисы могут исчезнуть в любой момент

Forbes
Без границ: зачем создавать сервис для инвалидов-путешественников Без границ: зачем создавать сервис для инвалидов-путешественников

Globe4all развивает путешествия для людей с ограниченными возможностями

Inc.
«Места, пропитанные ненавистью, лишь плодят ненависть». Отрывок из книги об экскурсиях в лагеря смерти «Места, пропитанные ненавистью, лишь плодят ненависть». Отрывок из книги об экскурсиях в лагеря смерти

Отрывок из книги «Монстр памяти» Ишая Сарида

СНОБ
Вы знали, сколько это стоит? 10 фильмов с самыми дорогими спецэффектами Вы знали, сколько это стоит? 10 фильмов с самыми дорогими спецэффектами

Зрелищные кинокартины, на создание которых были потрачены миллионы долларов

Cosmopolitan
Нужен характер Нужен характер

В борьбе с раком молочной железы многое зависит от решимости пациенток

Cosmopolitan
Как изменились Пименова, Блондо и другие самые красивые в мире девочки Как изменились Пименова, Блондо и другие самые красивые в мире девочки

Их называли самыми красивыми девочками в мире. Что же изменилось?

Cosmopolitan
Ivan Is Back Ivan Is Back

Алексей Чадов — сценарист, режиссер и актер в фильме «Своя война»

OK!
Непрофессионализм и ограничения: что мешает пивоварам работать с футбольными клубами в России Непрофессионализм и ограничения: что мешает пивоварам работать с футбольными клубами в России

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

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

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

Популярная механика
Вам осталось 300 книг. Начните читать прямо сейчас Вам осталось 300 книг. Начните читать прямо сейчас

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

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

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

СНОБ
После «оттепели». «Способ неопасного диссидентства» После «оттепели». «Способ неопасного диссидентства»

Юлию, оставшуюся фактически сиротой, удочерили старшие Хрущёвы

Дилетант
Почему китайские смартфоны такие дешевые: мифы и правда Почему китайские смартфоны такие дешевые: мифы и правда

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

CHIP
10 автомобилей, опередивших своё время 10 автомобилей, опередивших своё время

Нам повезло – мы живём в золотой век автомобилестроения

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

Что науке известно об идеальном кофе

N+1
Отношения с абьюзером — путь к посттравматическому расстройству Отношения с абьюзером — путь к посттравматическому расстройству

Что такое посттравматическое расстройство и как с ним бороться

Psychologies
Сбой в работе WhatsApp, Instagram и Facebook: как он на нас повлиял Сбой в работе WhatsApp, Instagram и Facebook: как он на нас повлиял

Сбой в Facebook. Многие назвали произошедшее настоящим Апокалипсисом

Psychologies
Как стартапер из Кемерово запустил сервис доставки еды в США и попал в рейтинг Forbes Как стартапер из Кемерово запустил сервис доставки еды в США и попал в рейтинг Forbes

Виталий Александров запустил сервис экспресс-доставки еды в США

Forbes
Сотворение Адама Сотворение Адама

За что все (и мы) любят Адама Драйвера

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

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

Cosmopolitan
На долгую память: как повысить стойкость перманентного макияжа На долгую память: как повысить стойкость перманентного макияжа

Перманентный макияж был создан для тех, кому не по душе заботы о красоте

Cosmopolitan
Путешествие на край детства Путешествие на край детства

Ксения Рождественская о «Маленькой маме» Селин Сьямма

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