Рассказываем о неравенстве 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
Кому и за что дали Нобелевские премии по естестественным наукам в 2021 году Кому и за что дали Нобелевские премии по естестественным наукам в 2021 году

Выбор лауреатов Нобелевской премии показывает текущее состояние мировой науки

СНОБ
Северный олень добрался до испанской Атапуэрки не меньше 243 тысяч лет назад Северный олень добрался до испанской Атапуэрки не меньше 243 тысяч лет назад

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

N+1
Торнадо многозадачности: как использовать «соковыжималку» для борьбы с тревогой Торнадо многозадачности: как использовать «соковыжималку» для борьбы с тревогой

Отрывок из книги «Разберись с тревогой» Риса Уильямс

Forbes
Используй ложку и телефон: 20 способов доставить себе удовольствие Используй ложку и телефон: 20 способов доставить себе удовольствие

Двадцать разных способов мастурбации на любой вкус и цвет

Cosmopolitan
Моделирование предсказало существование устойчивых двойных систем сверхмассивных черных дыр Моделирование предсказало существование устойчивых двойных систем сверхмассивных черных дыр

Астрофизики предположили существование двойных систем сверхмассивных черных дыр

N+1
Первый гирокар в истории: изобретение русского графа Шиловского Первый гирокар в истории: изобретение русского графа Шиловского

Гирокар - это автомобиль, имеющий два или более колёса, расположенных в линию

Популярная механика
Страховка «без границ» Страховка «без границ»

К 2030 году Россия должна войти в число мировых лидеров по экспорту

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

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

Forbes
Такая разная головная боль Такая разная головная боль

Головная боль, или цефалгия – самый распространенный симптом на планете

Здоровье
«Еще! Дай еще!»: как правильно обсуждать деньги в отношениях «Еще! Дай еще!»: как правильно обсуждать деньги в отношениях

Как обсудить финансы в отношениях и не расстаться?

Cosmopolitan
Диджитал-этикет для взрослых: журналисты WSJ составили ряд рекомендаций о цифровой этике и гигиене Диджитал-этикет для взрослых: журналисты WSJ составили ряд рекомендаций о цифровой этике и гигиене

Как выглядит цифровой этикет в современном мире?

Inc.
Понаехали! Понаехали!

Было время — Москву наводнили зарубежные звезды первой категории

Tatler
Евгений Гришковец — о «Живом журнале», хейтерах и о том, как интернет мешает ремеслу Евгений Гришковец — о «Живом журнале», хейтерах и о том, как интернет мешает ремеслу

Евгений Гришковец — чему его научил ЖЖ?

Esquire
Одна вокруг света: ремонт машины в Панаме и охота на голубых крабов Одна вокруг света: ремонт машины в Панаме и охота на голубых крабов

140-я серия о кругосветном путешествии москвички Ирины Сидоренко: Панама

Forbes
Читать, бояться! Триллеры, от которых мурашки по коже Читать, бояться! Триллеры, от которых мурашки по коже

12 страшных книжек для осеннего чтения

Cosmopolitan
Победили в Победили в

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

Cosmopolitan
Ловушка ложной скромности: почему самореклама не ругательство, а залог успеха Ловушка ложной скромности: почему самореклама не ругательство, а залог успеха

Отрывок из книги Стефани Сворд-Уильямс «К черту скромность!»

Forbes
На Мальорке обнаружили древний бронзовый меч балеарского типа На Мальорке обнаружили древний бронзовый меч балеарского типа

Археологи обнаружили бронзовый меч балеарского типа 793 года до нашей эры

N+1
«Она постоянно растет и мешает мне жить». Женщина пожаловалась на большую грудь «Она постоянно растет и мешает мне жить». Женщина пожаловалась на большую грудь

Мелисса-Мэй Лита стала недовольна рекордно большим бюстом

Cosmopolitan
Почку генетически модифицированной свиньи впервые подключили к человеку Почку генетически модифицированной свиньи впервые подключили к человеку

Она проработала три дня и не вызвала отторжения

N+1
Как менялась Светлана Светличная: актриса, красоту которой не признавали в СССР Как менялась Светлана Светличная: актриса, красоту которой не признавали в СССР

Как выглядела кинодива Светлана Светличная в разные годы своей долгой карьеры

Cosmopolitan
«Боль — это побочный эффект взросления»: психолог Илсе Санд о влиянии детских травм «Боль — это побочный эффект взросления»: психолог Илсе Санд о влиянии детских травм

Илсе Санд — о том, зачем она ушла из церкви и как справляться с болью

Forbes
«Точное мышление в безумные времена. Венский кружок и крестовый поход за основаниями науки» «Точное мышление в безумные времена. Венский кружок и крестовый поход за основаниями науки»

Карл Зигмунд рассказывает историю сообщества ученых и их научных изысканий

N+1
Мир копий и двойников: зачем нужна цифровая обработка геометрии Мир копий и двойников: зачем нужна цифровая обработка геометрии

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

Популярная механика
Ножом по стеклу: почему нас бесят звуки и какие раздражают сильнее всех Ножом по стеклу: почему нас бесят звуки и какие раздражают сильнее всех

Какие звуки раздражают нас сильнее всего и почему это происходит

Cosmopolitan
«Игра в кальмара»: почему все подсели на сериал, где убивают людей? «Игра в кальмара»: почему все подсели на сериал, где убивают людей?

Ликбез по сериалу «Игра в кальмара» без спойлеров

Maxim
Игра в десятку. Сколько будет стоить новый Lexus LX600 Игра в десятку. Сколько будет стоить новый Lexus LX600

Lexus LX600. Ну и чем он хорош?

Maxim
Профессия – стример: как делать деньги на прямых эфирах Профессия – стример: как делать деньги на прямых эфирах

Как стать стримером

Cosmopolitan
Купе на двоих Купе на двоих

Сейди Хаарла, рассказала о любви к поездам, одиночестве и русском языке

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