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

Паралимпиада в Токио принесла Андрею Калине сразу три золотых медали

Собака.ru
У берегов Явы обнаружили обломки черепов поздних эректусов У берегов Явы обнаружили обломки черепов поздних эректусов

Впервые были описаны фрагменты черепов архаичных людей, поднятые у острова Ява

N+1
Наши тритоны Наши тритоны

Мини-пруд на садовом участке — интересный опыт общения с природой

Наука и жизнь
Саудовская Аравия Саудовская Аравия

Люди, прошлое, религия, противоречия – и будущее

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

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

Cosmopolitan
Уже рядом: 5 отличных книг о будущем Уже рядом: 5 отличных книг о будущем

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

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

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

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

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

VC.RU
Как начать кататься на сноуборде Как начать кататься на сноуборде

Как встать на сноуборд, если раньше ты об этом только мечтала

Cosmopolitan
Девушка дня: Эмилия Кларк Девушка дня: Эмилия Кларк

Фото и факты из биографии Матери драконов – Эмилии Кларк

Maxim
За самозанятость! За самозанятость!

Почему самозанятость — это выгодно и удобно

Лиза
Эдгар Райт Эдгар Райт

Правила жизни кинорежиссера Эдгара Райта

Esquire
«Она капризная звезда»: Минаев рассказал, как уговорил Пугачёву выйти на сцену «Она капризная звезда»: Минаев рассказал, как уговорил Пугачёву выйти на сцену

Сергей Минаев рассказал о своем сотрудничестве с Аллой Пугачёвой

Cosmopolitan
Алгоритмическая реклама обещала экономию и прозрачную статистику, но стала жертвой ботов и клик-ферм Алгоритмическая реклама обещала экономию и прозрачную статистику, но стала жертвой ботов и клик-ферм

Что такое автоматизированная реклама, или программатик?

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

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

Esquire
«Что-то не так с Гэлвинами». Как одна семья помогла ученым исследовать природу шизофрении «Что-то не так с Гэлвинами». Как одна семья помогла ученым исследовать природу шизофрении

История семьи, в которой у шести детей из двенадцати диагностировали шизофрению

СНОБ
Лучшие хорроры 2021 года Лучшие хорроры 2021 года

Список самых любопытных хорроров года 2021 года

Esquire
«Цифра» против информации: почему мы не умеем использовать интернет «Цифра» против информации: почему мы не умеем использовать интернет

Чем плох словарь, которым мы активно пользуемся при описании интернета?

Forbes
Суттират Энн Ларларб – о том, как создавались образы Джеймса Бонда для фильма «Не время умирать» Суттират Энн Ларларб – о том, как создавались образы Джеймса Бонда для фильма «Не время умирать»

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

GQ
Анастасия Вертинская: Анастасия Вертинская:

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

Караван историй
Мужчина и его автомобиль: участники ГУМ Янгтаймер Ралли «Большая прогулка» и их ретрокары Мужчина и его автомобиль: участники ГУМ Янгтаймер Ралли «Большая прогулка» и их ретрокары

За что наши герои любят свои автомобили, что для них эпоха девяностых

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

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

РБК
Кодекс поведения робота Кодекс поведения робота

В чем заключаются ключевые проблемы взаимодействия человека и ИИ

Популярная механика
Присоединяй и властвуй Присоединяй и властвуй

Примеры объявления одним государством об аннексии другого

Дилетант
Физики не нашли нарушений CPT-симметрии в распадах ортопозитрония Физики не нашли нарушений CPT-симметрии в распадах ортопозитрония

Выполнение CPT-симметрии в процессах трехфотонного распада ортопозитрония

N+1
Актеры, которые напортачили в первый день съемок Актеры, которые напортачили в первый день съемок

И даже среди звезд кинематографа найдутся те, кто испортят все в первый день!

Maxim
Есть ли связь между усложнением общества и уменьшением размера мозга Есть ли связь между усложнением общества и уменьшением размера мозга

Почему человеческий мозг уменьшается?

СНОБ
Пошло все в баню Пошло все в баню

Банный комплекс, оформленный дизайнером Марией Водолацкой

AD
Не ровен час: зачем нужно точно измерять время и почему рабочие невзлюбили часы Не ровен час: зачем нужно точно измерять время и почему рабочие невзлюбили часы

Дэвид Руни рассказывает о 12 изобретениях, связанных с измерением времени

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