Рассказываем о неравенстве 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
Графен помог увидеть вигнеровский кристалл напрямую Графен помог увидеть вигнеровский кристалл напрямую

Способ визуализации вигнеровского кристалла с помощью графенового слоя

N+1
Зонд DART увидел омоложение поверхности Диморфа Зонд DART увидел омоложение поверхности Диморфа

Как планетологи составили портрет системы астероидов Дидим и Диморф

N+1
РПП: как лечить расстройства пищевого поведения РПП: как лечить расстройства пищевого поведения

Что такое РПП, какие они бывают и можно ли их вылечить

РБК
Милая агрессия и боязнь счастья: 5 необычных психологических явлений Милая агрессия и боязнь счастья: 5 необычных психологических явлений

Странные и забавные научные предположения о психологии человека

ТехИнсайдер
Эдвард Лир: «Большая книга чепухи». Новое издание классика бессмыслицы Эдвард Лир: «Большая книга чепухи». Новое издание классика бессмыслицы

Отрывок из книги путевых заметок Эдварда Лира

СНОБ
Когда смешно, уже не страшно Когда смешно, уже не страшно

Елена Новикова – о жизни за 50, отношениях с телом, детьми и своими страхами

Домашний Очаг
«Домашнее насилие и я: история Мии». Мия Бордман сняла фильм о бытовой тирании «Домашнее насилие и я: история Мии». Мия Бордман сняла фильм о бытовой тирании

Звезда телешоу «Teen Mom UK» сняла документальный фильм о домашнем насилии

Cosmopolitan
10 фильмов Хоакина Феникса 10 фильмов Хоакина Феникса

Вспоминаем важнейшие работы Хоакина Феникса

GQ
Я чувствовала себя как в клетке Я чувствовала себя как в клетке

История о том, как воля к победе творит чудеса

ПУСК
Уточненная модель снизила эффективность нейтронных звезд как детекторов темной материи Уточненная модель снизила эффективность нейтронных звезд как детекторов темной материи

Взаимодействие тяжелых частиц темной материи с нейтронами снизилось

N+1
6 фильмов, которые помогут поверить в себя 6 фильмов, которые помогут поверить в себя

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

Psychologies
Честные истории женщин, которые отказались от молока. И не пожалели! Честные истории женщин, которые отказались от молока. И не пожалели!

Почему отказ от молока — это нормально? Истории наших героинь

Cosmopolitan
Изменение климата сократило срок службы водохранилищ в высокогорной Азии Изменение климата сократило срок службы водохранилищ в высокогорной Азии

Тающие ледники размывают породу в горах и приносят больше осадка

N+1
План спасения: тренируем мышцы тазового дна План спасения: тренируем мышцы тазового дна

Врачи все чаще рекомендуют тренировать мышцы тазового дна

Домашний Очаг
5 полезных документальных фильмов о еде 5 полезных документальных фильмов о еде

Фильмы для тех, кто хочет знать, что он ест на самом деле.

GQ
Мужчина и его автомобиль: участники ГУМ Янгтаймер Ралли «Большая прогулка» и их ретрокары Мужчина и его автомобиль: участники ГУМ Янгтаймер Ралли «Большая прогулка» и их ретрокары

За что наши герои любят свои автомобили, что для них эпоха девяностых

Esquire
Русский суперфуд: 6 научных фактов о пользе и вреде квашеной капусты Русский суперфуд: 6 научных фактов о пользе и вреде квашеной капусты

Квашеная капуста — простое, но очень полезное блюдо

РБК
Отечественная жуть: 7 отличных российских хорроров Отечественная жуть: 7 отличных российских хорроров

Собрали семь российских ужастиков, которыми можно пугать не только детей

Cosmopolitan
Самые страшные вещи, которые люди видели в море Самые страшные вещи, которые люди видели в море

Отправляешься на берег моря с бархатным песочком? Не забудь электрошокер

VOICE
Три года в Долине строил мессенджер и закрыл его: что сделал не так Юрий Лифшиц и какие уроки вынес из провала Три года в Долине строил мессенджер и закрыл его: что сделал не так Юрий Лифшиц и какие уроки вынес из провала

Какие проблемы могут возникнуть при создании мессенджера — рассказал Юрий Лифшиц

VC.RU
Дина Рубина: В благодетельных дебрях психиатрии. Отрывок из романа «Маньяк Гуревич» Дина Рубина: В благодетельных дебрях психиатрии. Отрывок из романа «Маньяк Гуревич»

История страны и время, от которого можно спастись только в безумии

СНОБ
9 малоизвестных, но хороших советских фильмов (часть 2) 9 малоизвестных, но хороших советских фильмов (часть 2)

Самое время открыть для себя другую сторону советского кино

Maxim
Маргарита Митрофанова: «Я буду веселой старухой!» Маргарита Митрофанова: «Я буду веселой старухой!»

Маргарита Митрофанова о возрасте, эйджизме и позитивной старости

Psychologies
Девушка с характером Девушка с характером

Стать актрисой Леа Сейду было предначертано с самого рождения

Grazia
60 лет в комоде: девушка надела на свадьбу винтажное бабушкино платье 60 лет в комоде: девушка надела на свадьбу винтажное бабушкино платье

Элли Ливингвотер надела на свадьбу бабушкин наряд 60-летней давности

Cosmopolitan
«Я сгорала со стыда»: актриса Шанель Хэйес похудела на 60 кг «Я сгорала со стыда»: актриса Шанель Хэйес похудела на 60 кг

Шанель Хэйес (Chanelle Hayes) поделилась откровениями о проблемах с лишним весом

Cosmopolitan
Как накормить малоежку? Читай в новой книге Марики Кравцовой «Мама, хочу есть!» Как накормить малоежку? Читай в новой книге Марики Кравцовой «Мама, хочу есть!»

Марика Кравцова — о специфике детского питания и о том, как кормить детей

Cosmopolitan
Секрет — в брокколи Секрет — в брокколи

Ани Тейлор-Джой о триллере «Прошлой ночью в Сохо»

OK!
Анализ морфологии зубов опроверг гипотезу о заселении Америки из Японии Анализ морфологии зубов опроверг гипотезу о заселении Америки из Японии

Среди ученых продолжается дискуссия о времени и маршрутах заселения Америки

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