Рассказываем о неравенстве 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
Ваши внутренние часы устанавливают время приема пищи, которое снижает риск ожирения и диабета Ваши внутренние часы устанавливают время приема пищи, которое снижает риск ожирения и диабета

Зачем синхронизировать количество потребляемых калорий с циркадным ритмом?

ТехИнсайдер
Карина Андоленко. В потоке Карина Андоленко. В потоке

Карина Андоленко не боится залезть в кроличью нору и узнать что-то новое

Коллекция. Караван историй
30 способов перезапустить свое тело 30 способов перезапустить свое тело

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

kiozk originals
Киноварь приглянулась древним жителям Иберии в эпоху энеолита Киноварь приглянулась древним жителям Иберии в эпоху энеолита

Широкое использование киновари прекратилось лишь в эпоху ранней бронзы

N+1
Карта памяти для видеорегистратора: как выбрать? Карта памяти для видеорегистратора: как выбрать?

Какую карту памяти установить в видеорегистратор, и почему подойдет не любая?

CHIP
Без маски Без маски

Совсем другой Уилл Смит

GQ
Девушка дня: Эмилия Кларк Девушка дня: Эмилия Кларк

Фото и факты из биографии Матери драконов – Эмилии Кларк

Maxim
«У нас общий бюджет»: Ханна и Пашу тратят на домашний персонал 2 млн в месяц «У нас общий бюджет»: Ханна и Пашу тратят на домашний персонал 2 млн в месяц

Ханна (Анна Иванова) и Пашу (Павел Курьянов) готовы щедро платить за комфорт

Cosmopolitan
«Все родственники стали смотреть “Доту”». Интервью с киберспортсменами Team Spirit, которые выиграли 18 миллионов долларов «Все родственники стали смотреть “Доту”». Интервью с киберспортсменами Team Spirit, которые выиграли 18 миллионов долларов

«Сноб» поговорил с Team Spirit об их образе жизни, страхах и мечтах

СНОБ
Клин клином вышибают: когда белковая и углеводная диеты могут работать одинаково Клин клином вышибают: когда белковая и углеводная диеты могут работать одинаково

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

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

История самого юного узника концлагеря

Cosmopolitan
Ошибка 0xc0000005 при запуске игры или приложения: как ее исправить Ошибка 0xc0000005 при запуске игры или приложения: как ее исправить

Ошибка 0xc0000005: почему она возникает и как её исправить?

CHIP
10 пейзажей, которые неузнаваемо изменило время 10 пейзажей, которые неузнаваемо изменило время

Старые и современные фотографии мест, разница между которыми впечатляет

Maxim
Вождь индейки Вождь индейки

Агрохолдинг Наума Бабаева «Дамате» вскоре может стать самым крупным

Esquire
Наладили производство подделок и обманули Лувр: как братья из Одессы заработали на фальшивых древностях Наладили производство подделок и обманули Лувр: как братья из Одессы заработали на фальшивых древностях

Купцы из Одессы продали Франции подделку под видом древней золотой тиары

VC.RU
Многолетнюю мерзлоту нарекли ненадежным местом захоронения опасных отходов Многолетнюю мерзлоту нарекли ненадежным местом захоронения опасных отходов

Таяние вечной мерзлоты может высвободить огромное количество токсичных веществ

N+1
Кислотность Кислотность

Что мы знаем о кислотности желудочного сока?

Maxim
Апгрейд мозга: как развить интеллект и обмануть старость Апгрейд мозга: как развить интеллект и обмануть старость

Как «прокачать» свой мозг и одновременно замедлить процесс старения организма

Inc.
Любовь к миндалю: почему это хорошо Любовь к миндалю: почему это хорошо

Миндаль хорош и в качестве перекуса, и как ингредиент различных блюд

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

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

Maxim
Вопрос цены: почему при лобовых столкновениях пассажиры более дорогого автомобиля выживают чаще Вопрос цены: почему при лобовых столкновениях пассажиры более дорогого автомобиля выживают чаще

Влияет ли стоимость автомобиля на безопасность пассажиров?

Популярная механика
Долгие проводы — лишние слезы: «Не время умирать» — чересчур драматичный финал бондианы с Дэниелом Крейгом Долгие проводы — лишние слезы: «Не время умирать» — чересчур драматичный финал бондианы с Дэниелом Крейгом

«Не время умирать» — пышные проводы Дэниела Крейга в качестве Джеймса Бонда

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

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

4x4 Club
Как для советского кино строили соборы и создавали чудовищ Как для советского кино строили соборы и создавали чудовищ

Вспоминаем советское кино с самыми впечатляющими декорациями

Культура.РФ
Инженеры сами не знали, что умеет программа, а пользователи просили её упростить: так Microsoft создавала Office в 90-х Инженеры сами не знали, что умеет программа, а пользователи просили её упростить: так Microsoft создавала Office в 90-х

Как начинался путь Microsoft — рассказывает вице-президент Windows

VC.RU
Сто лет одиночества: почему мы не можем построить отношения? Сто лет одиночества: почему мы не можем построить отношения?

Почему мы так сильно хотим сблизиться с кем-то и все равно остаемся одни

Psychologies
Наталия Мещанинова — о праве на «не хочу» и спасении в стендапе Наталия Мещанинова — о праве на «не хочу» и спасении в стендапе

Режиссер и сценарист сериала «Пингвины моей мамы» — Наталия Мещанинова

РБК
10 вещей, от которых стоит отказаться, чтобы изменить жизнь к лучшему 10 вещей, от которых стоит отказаться, чтобы изменить жизнь к лучшему

Не только алкоголь и курение: от каких вредных привычек стоит отказаться

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