Рассказываем о неравенстве 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
«Он просто исчез»: почему с нами так поступают? «Он просто исчез»: почему с нами так поступают?

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

Psychologies
NASA обнаружило на Марсе «редкие сокровища», пролежавшие там миллиарды лет NASA обнаружило на Марсе «редкие сокровища», пролежавшие там миллиарды лет

Марсоход NASA обнаружил множество древних камней на краю кратера Езеро

Inc.
Кому мы нужны? Кому мы нужны?

Что поможет подружиться с диджитал-технологиями и построить карьеру в Сети?

Psychologies
Как кофеин влияет на мозг и тело: неожиданные факты Как кофеин влияет на мозг и тело: неожиданные факты

Исследования выявили ряд интересных фактов, связанных с кофеином

Psychologies
Теснота нестихового ряда Теснота нестихового ряда

Игорь Гулин о поэзии Сергея Кулле

Weekend
Гибкая личность: как избавиться от ярлыков и стать тем, кем хочешь Гибкая личность: как избавиться от ярлыков и стать тем, кем хочешь

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

РБК
Кто, где и как делает и продает суррогатный алкоголь в России. И почему трагедия в Оренбургской области может повториться Кто, где и как делает и продает суррогатный алкоголь в России. И почему трагедия в Оренбургской области может повториться

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

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

Вместе с открытием космоса придется перепридумать и язык человеческих эмоций

СНОБ
Спасите ваши уши: как наушники- Спасите ваши уши: как наушники-

Ученые увидели угрозу для здоровья в беспроводных наушниках

Playboy
Почему важно следить за давлением в шинах: советы водителям Почему важно следить за давлением в шинах: советы водителям

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

РБК
В США обнаружили обугленные семена табака возрастом более 12 тысяч лет В США обнаружили обугленные семена табака возрастом более 12 тысяч лет

Археологи обнаружили обугленные семена табака, возраст которых около 12300 лет

N+1
Культурные коды экономики: как холодная зима, язык и маскулинность влияют на страну Культурные коды экономики: как холодная зима, язык и маскулинность влияют на страну

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

Forbes
Майкл Холл – о возвращении Декстера, новом мире и сторонних проектах Майкл Холл – о возвращении Декстера, новом мире и сторонних проектах

Интервью с Майклом Холлом — о новом сезоне «Декстера» и своем персонаже

GQ
Солистка СБПЧ Евгения Борзых — о сказке для взрослых и силе одиночества Солистка СБПЧ Евгения Борзых — о сказке для взрослых и силе одиночества

Евгения Борзых — о музыкальной сказке группы СБПЧ и сериале «Большая секунда»

РБК
Николай первый Николай первый

Николай Полисский — первый российский художник работающий в жанре ленд-арт

AD
О чем не расскажут риэлторы: безопасно ли жить там, где кто-то умер? О чем не расскажут риэлторы: безопасно ли жить там, где кто-то умер?

Стоит ли избегать квартир, в которых произошла смерть?

Psychologies
Вопрос дня: сможет ли Илон Маск нарисовать свое лицо на поверхности Луны Вопрос дня: сможет ли Илон Маск нарисовать свое лицо на поверхности Луны

Портрет Илона Маска на Луне. Как вам такое?

Популярная механика
Своя морковка круглый год Своя морковка круглый год

Сеем морковку под зиму

Наука и жизнь
«День, когда я влюбилась в себя» «День, когда я влюбилась в себя»

Иногда самые близкие люди заставляют нас сомневаться в себе

Psychologies
«Шесть невозможностей: Загадки квантового мира» «Шесть невозможностей: Загадки квантового мира»

Отрывок из книги Джона Гриббина — как ученые объясняют события в квантовом мире

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

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

Коллекция. Караван историй
10 самых разочаровывающих туристических достопримечательностей мира 10 самых разочаровывающих туристических достопримечательностей мира

Оказывается, в мире полно туристических мест, которые стоит облетать стороной

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

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

Cosmopolitan
Как звезда «Игры в кальмара» набрала 16 млн подписчиков за три недели Как звезда «Игры в кальмара» набрала 16 млн подписчиков за три недели

Хо Ен Чон — самая популярная южнокорейская актриса в Instagram

РБК
Эсин Гюрал Аргат «Мне нравится быть в центре» Эсин Гюрал Аргат «Мне нравится быть в центре»

Турецкая бизнесвумен Эсин Гюрал Аргат — о бизнесе, женщинах и футболе

Forbes Woman
«Несуществующий» остров, гигантские губы и пентаграмма: 5 загадочных объектов на картах Google «Несуществующий» остров, гигантские губы и пентаграмма: 5 загадочных объектов на картах Google

Путешествовать по миру интересно, но не менее занятно изучать карту со спутника

Playboy
От первого в СССР магазина с западными стандартами до устаревшего ТЦ: история универмага «Москва» От первого в СССР магазина с западными стандартами до устаревшего ТЦ: история универмага «Москва»

История универмага «Москва»

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

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

Cosmopolitan
Марина Казанкова: Марина Казанкова:

Интервью с актрисой Мариной Казанковой

Караван историй
Открыть в приложении