Рассказываем о неравенстве 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
«Беременная жена гонит меня ночью за мороженым. Это манипуляция?» «Беременная жена гонит меня ночью за мороженым. Это манипуляция?»

Что делать, если беременная жена просит мороженое в 3 часа ночи?

Psychologies
Ученые заявили, что дисциплина не поможет побороть лишний вес. Дело в другом Ученые заявили, что дисциплина не поможет побороть лишний вес. Дело в другом

Похудение — это битва, выходящая за рамки чистой силы воли

Inc.
Психологические факты, которые изменят вашу жизнь Психологические факты, которые изменят вашу жизнь

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

Psychologies
6 признаков глупого человека 6 признаков глупого человека

Как понять, кого нужно избегать? Да и нужно ли на самом деле?

Psychologies
Понаехали! Понаехали!

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

Tatler
Битва за кроссовки: магазины борются против ботов-перекупщиков, чтобы дать шанс обывателям, и в итоге проигрывают сами Битва за кроссовки: магазины борются против ботов-перекупщиков, чтобы дать шанс обывателям, и в итоге проигрывают сами

Лимитированную обувь невозможно купить из-за ботов-перекупщиков

VC.RU
Звезда сериала «Игра в кальмара» Чон Хо Ен: от модели с характером до мировой знаменитости Звезда сериала «Игра в кальмара» Чон Хо Ен: от модели с характером до мировой знаменитости

Актриса Чон Хо Ен стала настоящей звездой.

Maxim
Ведьма с Уолл-стрит: самая богатая и самая скупая женщина в мире Ведьма с Уолл-стрит: самая богатая и самая скупая женщина в мире

Беттми Грин: история о том, как не нужно обращаться с деньгами

Cosmopolitan
19 безобразных архитектурных решений российских городов 19 безобразных архитектурных решений российских городов

Русская урбанистика, бессмысленная и беспощадная

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

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

Forbes
Дети, разводы и лишние килограммы: легендарные «Друзья» 27 лет спустя Дети, разводы и лишние килограммы: легендарные «Друзья» 27 лет спустя

Как выглядят и чем живут актеры «Друзей»?

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

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

Inc.
Дохлая жаба и папирус: как женщины справлялись с месячными в прошлом Дохлая жаба и папирус: как женщины справлялись с месячными в прошлом

Чем бы нам пришлось пользоваться, если б мы жили в Древнем Египте

Cosmopolitan
Анжела Хачатурьян. Стальная леди советского шоу-биза Анжела Хачатурьян. Стальная леди советского шоу-биза

Анжела Хачатурьян. Стальная леди советского шоу-биза

Коллекция. Караван историй
3D-печать позволила получить магнитный сплав из немагнитных веществ 3D-печать позволила получить магнитный сплав из немагнитных веществ

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

Популярная механика
Цифровые дороги: кто и зачем делает трассы умными Цифровые дороги: кто и зачем делает трассы умными

Мы живем в эпоху цифровых двойников. У современных дорог они тоже есть

Популярная механика
«Пьяный» секс: самые распространенные мифы и правда «Пьяный» секс: самые распространенные мифы и правда

Можно ли использовать алкоголь в качестве прелюдии и предисловия к сексу?

Maxim
Гора защитила превращение фтора в кислород от космической радиации Гора защитила превращение фтора в кислород от космической радиации

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

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

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

Cosmopolitan
Елена Нусинова — Forbes: «Сейчас говорить о журналистике почти невыносимо» Елена Нусинова — Forbes: «Сейчас говорить о журналистике почти невыносимо»

Как женщины заняли топовые позиции в российской журналистике в 1990-е?

Forbes
12 апокалипсисов, которые так и не произошли 12 апокалипсисов, которые так и не произошли

12 концов света, которые человечеству удалось пережить вполне благополучно

Maxim
Мотивация, выбор, прогресс: как работать с лучшими сотрудниками Мотивация, выбор, прогресс: как работать с лучшими сотрудниками

Области, на которых нужно сосредоточиться при наставничестве хороших сотрудников

VC.RU
Ана де Армас: бывшая девушка Аффлека и новая девушка Бонда Ана де Армас: бывшая девушка Аффлека и новая девушка Бонда

Как Ана де Армас переехала в Мадрид с 300 евро и как решилась покорить Голливуд

Cosmopolitan
«Это смерть за мной приходила»: как самопрограммирование сводит нас в могилу «Это смерть за мной приходила»: как самопрограммирование сводит нас в могилу

Отрывок из книги «Фокус на жизнь» — глава о самореализующихся пропрочествах

Forbes
Самая известная советская эскортница: как сложилась судьба «Интердевочки» Самая известная советская эскортница: как сложилась судьба «Интердевочки»

Елена Яковлева с детства знала, что станет актрисой

Cosmopolitan
Советы советского хирурга, дожившего до 104 лет: 12 правил долголетия Советы советского хирурга, дожившего до 104 лет: 12 правил долголетия

Рекомендации о том, как продлить свою жизнь и оставаться бодрым

Cosmopolitan
Археологи обнаружили большой римский храм в финикийском городе Тир Археологи обнаружили большой римский храм в финикийском городе Тир

Археологи обнаружили большой храм на самой высокой точке города Тир

N+1
«У нас есть план А, план Б и план Х» Юлия Пересильд — о съемках в космосе «У нас есть план А, план Б и план Х» Юлия Пересильд — о съемках в космосе

Юлия Пересильд рассказывает, как готовится к полету на МКС

РБК
Советская автомобильная иллюстрация: 1976 год Советская автомобильная иллюстрация: 1976 год

Необычная автомобильная подборка – из набора карманных календариков 1976 года

Популярная механика
Открыть в приложении