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

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

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

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

«Турецкие войны России: Царская армия и балканские народы в XIX столетии» «Турецкие войны России: Царская армия и балканские народы в XIX столетии»

Каким было отношение населения Румелии к российской армии

N+1
Поселившийся в аду Орфей. Как Георгий Иванов из любимца муз и бонвивана стал самым глубоким и печальным поэтом русской эмиграции Поселившийся в аду Орфей. Как Георгий Иванов из любимца муз и бонвивана стал самым глубоким и печальным поэтом русской эмиграции

Его называли «первым поэтом русской эмиграции», а еще «ничтожным эпигоном»

Esquire
Гремучие змеи попили воды с тел сородичей Гремучие змеи попили воды с тел сородичей

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

N+1
Делал дизайн, пока говорил по телефону: история Пола Рэнда, который создал логотипы для IBM и Стива Джобса Делал дизайн, пока говорил по телефону: история Пола Рэнда, который создал логотипы для IBM и Стива Джобса

Пол Рэнд работал арт-директором в Esquire и делал рекламу на азбуке Морзе

VC.RU
Важная деталь делового стиля: как правильно стирать галстуки, чтобы они выглядели великолепно Важная деталь делового стиля: как правильно стирать галстуки, чтобы они выглядели великолепно

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

ТехИнсайдер
Пляжи, затонувшие корабли, крепости: чем заняться в Кабо-Верде Пляжи, затонувшие корабли, крепости: чем заняться в Кабо-Верде

Как живет и чем развлекает африканская республика Кабо-Верде

РБК
Плохой ботокс: у девушки перекосилось лицо после неудачного укола в подбородок Плохой ботокс: у девушки перекосилось лицо после неудачного укола в подбородок

Тиктокерша поделилась историей о том, как неудачный укол ботокса изменил её лицо

Cosmopolitan
Платформы говорят Платформы говорят

Cтриминговые сервисы множатся и производят огромное количество контента

GQ
Забил 144 гола, стал участником секс-скандала и ругался с Карпиным. Топ-10 фактов о лучшем футболисте страны Артеме Дзюбе Забил 144 гола, стал участником секс-скандала и ругался с Карпиным. Топ-10 фактов о лучшем футболисте страны Артеме Дзюбе

Самые громкие истории, связанные с Артемом Дзюбой

Maxim
Нейрохирург и чемпион по памяти назвали 5 способов лучше запоминать имена новых знакомых Нейрохирург и чемпион по памяти назвали 5 способов лучше запоминать имена новых знакомых

5 способов лучше запоминать имена от нейрохирурга и мирового чемпиона по памяти

Inc.
«Ни одного года мы не ели хлеба вволю» «Ни одного года мы не ели хлеба вволю»

«В соседнем селе 7 июня умерли с голоду в один день шестнадцать человек»

Наука
Сильная и зависимая: как становятся жертвой абьюза благополучные женщины Сильная и зависимая: как становятся жертвой абьюза благополучные женщины

Как жертвами абьюза становятся женщины, которые, кажется, от этого застрахованы

Cosmopolitan
Субфебрильная температура: что делать, когда держатся 37°С Субфебрильная температура: что делать, когда держатся 37°С

Что делать с температурой, если она поднялась выше 37 °С, но ниже 38 °С?

РБК
Строит магазины без окон, чтобы люди теряли счёт времени и думали о покупках: как IKEA заставляет тратить больше Строит магазины без окон, чтобы люди теряли счёт времени и думали о покупках: как IKEA заставляет тратить больше

Большая часть продаж IKEA приходится на незапланированные покупки посетителей

VC.RU
Искусство убеждать: 14 правил ведения сложных переговоров Искусство убеждать: 14 правил ведения сложных переговоров

Отрывок из книги «Убедить дракона» — об особенностях ведения переговоров

Inc.
Как накормить малоежку? Читай в новой книге Марики Кравцовой «Мама, хочу есть!» Как накормить малоежку? Читай в новой книге Марики Кравцовой «Мама, хочу есть!»

Марика Кравцова — о специфике детского питания и о том, как кормить детей

Cosmopolitan
Вторичный рынок Jeep Renegade. Итальянский внук американского дедушки Вторичный рынок Jeep Renegade. Итальянский внук американского дедушки

Jeep Renegade — отличное сочетание озорной внешности и отличной динамики

4x4 Club
«Когда геоданные попадают на рынок, их можно перепродавать бесконечно»: как устроен рынок сведений о местоположении «Когда геоданные попадают на рынок, их можно перепродавать бесконечно»: как устроен рынок сведений о местоположении

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

VC.RU
Русский суперфуд: 6 научных фактов о пользе и вреде квашеной капусты Русский суперфуд: 6 научных фактов о пользе и вреде квашеной капусты

Квашеная капуста — простое, но очень полезное блюдо

РБК
Кто на свете всех умнее Кто на свете всех умнее

Каким может быть современный умный дом?

Tatler
Екатерина Климова: Если хочешь чего-то большего, сделай это сама Екатерина Климова: Если хочешь чего-то большего, сделай это сама

Екатерина Климова – о семейных буднях, женском счастье и, конечно, о красоте

Добрые советы
Дирижабли, визы и рулетка: как и зачем путешествовали в первой половине XX века Дирижабли, визы и рулетка: как и зачем путешествовали в первой половине XX века

Как, куда и ради чего ехали путешественники в первой трети XX века

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

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

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

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

Cosmopolitan
Как запустить стартап без денег (пошаговая инструкция) Как запустить стартап без денег (пошаговая инструкция)

Можно ли построить полноценный бизнес без денег?

Inc.
4 странные попытки великих людей написать книги и что из этого вышло 4 странные попытки великих людей написать книги и что из этого вышло

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

Maxim
Честные истории женщин, которые отказались от молока. И не пожалели! Честные истории женщин, которые отказались от молока. И не пожалели!

Почему отказ от молока — это нормально? Истории наших героинь

Cosmopolitan
Ученые устроили австралийским комарам бактериальный геноцид Ученые устроили австралийским комарам бактериальный геноцид

Ученые смогли подавить численность комаров в двух австралийских городах

N+1
Удивительные деревянные механизмы Дерека Хаггера Удивительные деревянные механизмы Дерека Хаггера

Работы Дерека Хаггера – из тех, которые стоит повторить самостоятельно.

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

Отрывкок из книги «Возникновение новой науки о человеческой психике»

N+1
Открыть в приложении