Рассказываем о неравенстве 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
Блогер Verona: «Моя уникальность не в лишнем весе» Блогер Verona: «Моя уникальность не в лишнем весе»

Инстаблогера Верону Берникову знают, благодаря ее зажигательным танцам и шуткам

Cosmopolitan
Древняя ДНК указала на обмен генами между охотниками-собирателями Северной Африки и Европы Древняя ДНК указала на обмен генами между охотниками-собирателями Северной Африки и Европы

Население Восточного Магриба сохраняло преемственность от охотников-собирателей

N+1
«‎Наш новый сотрудник — искусственный интеллект». Как подготовиться к появлению цифрового коллеги «‎Наш новый сотрудник — искусственный интеллект». Как подготовиться к появлению цифрового коллеги

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

СНОБ
Партнер-провокатор: что стоит за его манипуляциями и как реагировать правильно Партнер-провокатор: что стоит за его манипуляциями и как реагировать правильно

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

Psychologies
Время старших Время старших

Как мы осознаем сегодня возраст? Рассуждают участницы сообщества Young Old

Домашний Очаг
Жена поспорила с мужем и перестала убирать в доме – вот что из этого вышло Жена поспорила с мужем и перестала убирать в доме – вот что из этого вышло

Что делать, если кто-то уверен, что всё домашнее хозяйство держится на нем?

Cosmopolitan
Автомобили на дровах: как технологии СССР помогут пережить апокалипсис на колесах Автомобили на дровах: как технологии СССР помогут пережить апокалипсис на колесах

Каждый, кто слышит про машины на дровах, первым делом восклицает: «Бред!»

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

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

РБК
Я так вижу Я так вижу

Выставка Lady Dior As Seen By наконец приехала в Москву!

Grazia
Оттенки премиального: кроссовер Genesis GV70 Оттенки премиального: кроссовер Genesis GV70

Кроссовер Genesis GV70 коварно заманивает своим богатым внутренним миром

Maxim
Хлеб и говядина: ученые назвали самые вредные продукты в мире Хлеб и говядина: ученые назвали самые вредные продукты в мире

Если ты слышишь словосочетание «вредные продукты», то что представляешь?

Cosmopolitan
Вертикаль Вертикаль

Что и на какой высоте ждет вас при подъеме от Земли

N+1
По горизонтали: что предложить сотруднику, кроме повышения По горизонтали: что предложить сотруднику, кроме повышения

Развитие карьеры по горизонтали — что это такое?

Inc.
Логический кубит стал устойчив к шумам Логический кубит стал устойчив к шумам

Квантовые коды коррекции ошибок работают не только в теории, но и на практике

N+1
8 фильмов, которые стоит посмотреть начинающим любителям кино 8 фильмов, которые стоит посмотреть начинающим любителям кино

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

GQ
«Злость или зависть посещают нас не без причины»: как стоически принимать эмоции «Злость или зависть посещают нас не без причины»: как стоически принимать эмоции

Наш разум постоянно и неизбежно проделывает трюки с реальностью

Forbes
В сперме не было ни одного сперматозоида: как я перенесла неудачную попытку ЭКО В сперме не было ни одного сперматозоида: как я перенесла неудачную попытку ЭКО

Беременность не всегда наступает быстро

Cosmopolitan
Детки – не конфетки и не булочки Детки – не конфетки и не булочки

Как не вырастить ребёнка полным

Здоровье
6 возможных причин психологических травм 6 возможных причин психологических травм

Не всякая психотравма громко заявляет о себе — мы можем и не подозревать

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

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

Maxim
История первой и единственной кошки в космосе История первой и единственной кошки в космосе

Как кошка С 341 стала первой космонавткой

Maxim
«У нас есть план А, план Б и план Х» Юлия Пересильд — о съемках в космосе «У нас есть план А, план Б и план Х» Юлия Пересильд — о съемках в космосе

Юлия Пересильд рассказывает, как готовится к полету на МКС

РБК
«Просто попроси»: когда этому правилу не место в браке и отношениях «Просто попроси»: когда этому правилу не место в браке и отношениях

В каких случаях правилу «Просто попроси» не место в браке

Cosmopolitan
Человек и ледокол Человек и ледокол

Евгений Гришковец рассказал, каково это – пройти сквозь льды к Северному полюсу

Men’s Health
Закулисье дома гламура и жадности Закулисье дома гламура и жадности

История семейства Гуччи буквально просилась на экран

Караван историй
«Это вам не красивое кино». Женщина рассказала, как стала частным детективом «Это вам не красивое кино». Женщина рассказала, как стала частным детективом

Александра Квик уже год как бросила работу бухгалтера и стала частным детективом

Cosmopolitan
Online как повод для знакомства Online как повод для знакомства

Кого мы ищем в виртуальном пространстве и кого находим?

Psychologies
Беата Маковская. Одесский дворик Беата Маковская. Одесский дворик

Беата Маковская: «Я не думала, что после «Ликвидации» проснусь знаменитой»

Коллекция. Караван историй
По законам тундры По законам тундры

В северных регионах страны развивают традиционное оленеводство

Агроинвестор
Открыть в приложении