Рассказываем о неравенстве 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
Невозможно сдержать слезы: история дружбы Вина Дизеля и Пола Уокера Невозможно сдержать слезы: история дружбы Вина Дизеля и Пола Уокера

Как коллеги из "Форсажа" стали друзьями и названными братьями

Cosmopolitan
Робопчелу научили садиться по-комарьи Робопчелу научили садиться по-комарьи

Инженеры разработали шасси для миниатюрного орнитоптера RoboBee

N+1
Самые опасные декольте: звезды с пышной грудью, которые выбирают вырезы поглубже Самые опасные декольте: звезды с пышной грудью, которые выбирают вырезы поглубже

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

Cosmopolitan
Борьба со старением: новые подходы и тренды Борьба со старением: новые подходы и тренды

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

РБК
Первых кроманьонцев заподозрили в охоте на хищников ради меха и материалов для украшений Первых кроманьонцев заподозрили в охоте на хищников ради меха и материалов для украшений

Археологи проанализировали фаунистический материал из пещеры Бачо-Киро

N+1
Топ-5 самых странных моментов бондианы Топ-5 самых странных моментов бондианы

Даже в фильмах о легендарном спецагенте есть киноляпы

Maxim
Британские онкологи связали прием каннабидиола с регрессом рака легкого у 80-летней пациентки Британские онкологи связали прием каннабидиола с регрессом рака легкого у 80-летней пациентки

Может ли каннабидиол влиять на рак легких?

N+1
Как мобильные приложения помогают спать, отдыхать и снижать тревожность: 5 лучших сервисов Как мобильные приложения помогают спать, отдыхать и снижать тревожность: 5 лучших сервисов

Могут ли мобильные сервисы помочь справиться с тревожностью?

Популярная механика
«Игра в кальмара»: Человек играющий «Игра в кальмара»: Человек играющий

Почему вам обязательно нужно посмотреть «Игру в кальмара»

GQ
Музыкант и поэт Вадик Королев — о голосе-маске Музыкант и поэт Вадик Королев — о голосе-маске

Вадик Королев, участник групп OQJAV и «Королев Попова», размышляет о голосах

РБК
Какие животные умеют петь? Какие животные умеют петь?

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

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

Что делать, если вы поняли, что вашего близкого посещают суицидальные мысли?

Psychologies
10 прочнейших автомобилей, способных пересечь пустыню 10 прочнейших автомобилей, способных пересечь пустыню

Автомобили, способные пересечь пустыню не хуже тачек из «Безумного Макса»

Популярная механика
Всё плохо и ничего не болит: 5 признаков проблем с печенью Всё плохо и ничего не болит: 5 признаков проблем с печенью

Признаки, которые указывают на заболевания печени

Cosmopolitan
Тироль первого плана Тироль первого плана

Тироль не зря называют сердцем Альп

Men’s Health
Отеки, усталость, тяжесть: когда и зачем тебе нужен флеболог Отеки, усталость, тяжесть: когда и зачем тебе нужен флеболог

Ты тоже могла сталкиваться с тяжестью в ногах, характерным «гулом», отеками

Cosmopolitan
Как голос в наушниках помогает справиться с одиночеством Как голос в наушниках помогает справиться с одиночеством

Почему мы так полюбили слушать других

РБК
Брак втроем: что связывало Ленина, Крупскую и Арманд Брак втроем: что связывало Ленина, Крупскую и Арманд

«Партия прогулистов» — так называли эту троицу: Арманд, Крупскую и Ленина

Cosmopolitan
Наталья Петрова: «Пионеры Русской Америки» Наталья Петрова: «Пионеры Русской Америки»

Книга Натальи Петровой о тех, кто оставил значительный след в истории Аляски

СНОБ
Как омолодить лицо при помощи бровей: маскируем усталость и морщины Как омолодить лицо при помощи бровей: маскируем усталость и морщины

Если хочется выглядеть моложе, лучше возьми на вооружение наши советы

Cosmopolitan
Насколько полезен совет «бросай свою скучную работу и иди вперед к мечте» Насколько полезен совет «бросай свою скучную работу и иди вперед к мечте»

Стоит ли бросать все ради своей мечты?

GQ
5 лайхаков, которые уберегут деньги на вашем счету от мошенников 5 лайхаков, которые уберегут деньги на вашем счету от мошенников

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

CHIP
Бизнес на опечатках: в 50-х секретарше надоело ошибаться в документах, она взбила краску в блендере и создала корректор Бизнес на опечатках: в 50-х секретарше надоело ошибаться в документах, она взбила краску в блендере и создала корректор

Как секретарша изобрела корректор и сделала из своего гараж мини-завод

VC.RU
5 вредных привычек, которые заставляют нас стареть быстрее 5 вредных привычек, которые заставляют нас стареть быстрее

Ряд привычек может пагубно сказаться на состоянии нашего организма

Psychologies
В бирманском янтаре обнаружили миниатюрного краба В бирманском янтаре обнаружили миниатюрного краба

Это древнейший неморской краб, известный палеонтологам.

N+1
Агентство, студия, фриланс: какого подрядчика выбрать и как ему платить Агентство, студия, фриланс: какого подрядчика выбрать и как ему платить

Агентство, микроагентство, фриланс — чем они отличаются

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

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

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

Наши герои, отношения которых сложились по-разному

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

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

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