Рассказываем о неравенстве 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 вершинах, то есть некоторый набор вершин (точек), в котором некоторые пары вершин соединены ребрами (отрезками), а некоторые нет. Нужно выяснить, найдется ли такой циклический путь по ребрам графа, который по разу проходит через все вершины (гамильтонов цикл). Ясно, что объем перебора всевозможных путей в графе быстро растет с ростом числа вершин и ребер.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Оригами-робота научили прижимать ноги и ходить по-крабьи Оригами-робота научили прижимать ноги и ходить по-крабьи

Инженер из Германии разработал четвероногого оригами-робота Fold Walker

N+1
За пригоршню «спасибо» За пригоршню «спасибо»

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

Maxim
Злая шутка эволюции: почему птица додо совсем не такая, какой мы ее знаем Злая шутка эволюции: почему птица додо совсем не такая, какой мы ее знаем

Что мы знаем о дронте? Меньше, чем о мамонтах

ТехИнсайдер

19 кадров тех трех страшных дней 26 октября 2002 года

Cosmopolitan
Крупным планом: что происходит с отечественным кинорынком Крупным планом: что происходит с отечественным кинорынком

Какое кино сейчас интересно зрителям в России?

Inc.
Землетрясение назвали причиной гибели мужчины на Кипре более 1600 лет назад Землетрясение назвали причиной гибели мужчины на Кипре более 1600 лет назад

Этот мужчина погиб во время землетрясения в середине IV века нашей эры на Кипре

N+1
Аэродинамика скоростных поездов: почему ветер не мешает TGV Аэродинамика скоростных поездов: почему ветер не мешает TGV

Поезд TGV Париж – Нант отходит от парижского вокзала Монпарнас почти бесшумно

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

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

Forbes
Каково это – покупать картинки в интернете за миллионы долларов Каково это – покупать картинки в интернете за миллионы долларов

Исповедь Pranksy, NFT-коллекционера, чей точный возраст неизвестен

Esquire
Почему коренные зубы у человека вылезают так поздно: любопытная гипотеза Почему коренные зубы у человека вылезают так поздно: любопытная гипотеза

У Homo sapiens несколько зубов отрастают только в подростковом возрасте

Популярная механика
Умер легендарный лыжник Вячеслав Веденин, тот самый, кто придумал слово «дахусим» и не опустил флаг СССР перед императором Японии Умер легендарный лыжник Вячеслав Веденин, тот самый, кто придумал слово «дахусим» и не опустил флаг СССР перед императором Японии

Вячеслав Веденин. Легенда СССР, который показал характер на Олимпиаде 1972

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

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

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

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

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

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

Популярная механика
Пёс Лео, выкупленный у сербских активистов, спас владельца отеля в Италии от смерти и так нашёл себе рабочее место Пёс Лео, выкупленный у сербских активистов, спас владельца отеля в Италии от смерти и так нашёл себе рабочее место

Четвероногий друг спас владельца отеля от смерти во время наводнения

Популярная механика
Запеченные младенцы и муж рядом: как рожали на Руси Запеченные младенцы и муж рядом: как рожали на Руси

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

Cosmopolitan
Странные и смешные тени, сфотографированные при обычных обстоятельствах (галерея) Странные и смешные тени, сфотографированные при обычных обстоятельствах (галерея)

Авторам этих фотографий попалось, действительно, нечто особенное!

Maxim
Эдвард Радзинский. Прощальная гастроль клуба «418» Эдвард Радзинский. Прощальная гастроль клуба «418»

Эдвард Радзинский остается блистательным рассказчиком

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

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

Esquire
Не верь глазам своим. Автомобили, которые прикидываются другими брендами Не верь глазам своим. Автомобили, которые прикидываются другими брендами

Иногда автомобили, как совы, оказываются вовсе не тем, чем кажутся

Maxim
Антон Васильев. Катя и мужчины, которые ее любили... Антон Васильев. Катя и мужчины, которые ее любили...

Брат актрисы Екатерины Васильевой рассказывает о своей знаменитой семье

Коллекция. Караван историй
Кто этот мощный старик? Кто этот мощный старик?

Как старик сэр Ранульф Файнс покорил “крышу мира”

Men’s Health
«Однажды в сказке»: читаем ребенку вместе с Людмилой Петрановской «Однажды в сказке»: читаем ребенку вместе с Людмилой Петрановской

Отрывок из книги «Читаем и развиваемся с психологом. Однажды в сказке»

Psychologies
Черви-мусороеды, солнце в банке, съедобные бутылки: 5 значимых экоразработок последних 10 лет Черви-мусороеды, солнце в банке, съедобные бутылки: 5 значимых экоразработок последних 10 лет

5 экологических разработок, которые способны изменить жизнь на планете

Популярная механика
Что такое социальное здоровье и как его укрепить Что такое социальное здоровье и как его укрепить

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

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

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

Cosmopolitan
Падающие башни мира: не только Пизанская! Падающие башни мира: не только Пизанская!

Падающие башни — что с ними делать?

Популярная механика
К чему приведет одержимость соцсетями. Меган Анджело: Подписчики К чему приведет одержимость соцсетями. Меган Анджело: Подписчики

Отрывок из антиутопии «Подписчики» о разрушительном влиянии соцсетей

СНОБ
Виктор Рыжаков. Портрет охотника на снегу Виктор Рыжаков. Портрет охотника на снегу

Художественный руководитель театра «Современник» Виктор Рыжаков

СНОБ
Как мир перестал слышать архитекторов Как мир перестал слышать архитекторов

Проект Григория Ревзина «Оправдание утопии». Мишель Рагон: GIAP

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