Рассказываем о неравенстве 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 вершинах, то есть некоторый набор вершин (точек), в котором некоторые пары вершин соединены ребрами (отрезками), а некоторые нет. Нужно выяснить, найдется ли такой циклический путь по ребрам графа, который по разу проходит через все вершины (гамильтонов цикл). Ясно, что объем перебора всевозможных путей в графе быстро растет с ростом числа вершин и ребер.

Авторизуйтесь, чтобы продолжить чтение. Это быстро и бесплатно.

Регистрируясь, я принимаю условия использования

Рекомендуемые статьи

Мухи-журчалки начали точно подражать осам уже 33 миллиона лет назад Мухи-журчалки начали точно подражать осам уже 33 миллиона лет назад

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

N+1
Колики или нет? Колики или нет?

Как быстро снять дискомфорт в животике малыша?

Лиза
Японцы сделали роборуку с человеческими мышцами Японцы сделали роборуку с человеческими мышцами

Японские инженеры разработали биогибридную руку с человеческими мышцами

N+1
Актер года: Иван Янковский Актер года: Иван Янковский

Иван Янковский прошел через «Огонь» и «Топи»

GQ
Исследование выявило один фактор, по которому можно понять, что вы находитесь в здоровых отношениях Исследование выявило один фактор, по которому можно понять, что вы находитесь в здоровых отношениях

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

ТехИнсайдер
Самые низкорослые спортсмены в истории: футболист, боксер, баскетболист и другие Самые низкорослые спортсмены в истории: футболист, боксер, баскетболист и другие

Большие спортивные карьеры небольших людей

Maxim
Нельзя, запретить Нельзя, запретить

Героини, которые нашли свое призвание в «неженских» профессиях

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

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

N+1
Низкоуглеродное государство:  как снизить издержки энергоперехода Низкоуглеродное государство:  как снизить издержки энергоперехода

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

Forbes
5 лучших БДСМ-девайсов для сексуальных экспериментов 5 лучших БДСМ-девайсов для сексуальных экспериментов

Почему БДСМ - это нормально, и как плавно внедрить его в вашу жизнь

Playboy
Дорогу подскажет наша голограмма Дорогу подскажет наша голограмма

WayRay выпускает уникальные голографические системы навигации и помощи вождения

Эксперт
Игры кончились: 10 самых дорогих игрушек мира Игры кончились: 10 самых дорогих игрушек мира

Цены на эти игрушки совсем не детские, зато это настоящие произведения искусства

Cosmopolitan
«Просто попроси»: когда этому правилу не место в браке и отношениях «Просто попроси»: когда этому правилу не место в браке и отношениях

В каких случаях правилу «Просто попроси» не место в браке

Cosmopolitan
Мода 2000-х: самые безумные образы российских звезд Мода 2000-х: самые безумные образы российских звезд

Эра «гламура» 2000-х захлестнула весь мир, и Россия не стала исключением

VOICE
Расстрел отца, ссылка матери и голод: страшное детство великой Майи Плисецкой Расстрел отца, ссылка матери и голод: страшное детство великой Майи Плисецкой

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

Cosmopolitan
Графен помог увидеть вигнеровский кристалл напрямую Графен помог увидеть вигнеровский кристалл напрямую

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

N+1
Детские лагеря для взрослых: как они работают Детские лагеря для взрослых: как они работают

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

СНОБ
«Прощай, сестра»: история одного семейного крушения «Прощай, сестра»: история одного семейного крушения

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

Psychologies
«‎Наш новый сотрудник — искусственный интеллект». Как подготовиться к появлению цифрового коллеги «‎Наш новый сотрудник — искусственный интеллект». Как подготовиться к появлению цифрового коллеги

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

СНОБ
Все болезни — от нервов? Загадки психосоматики Все болезни — от нервов? Загадки психосоматики

Как именно наше душевное состояние влияет на тело?

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

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

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

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

Maxim
Живые часы Живые часы

Разгадка тайны биологических часов

Вокруг света
Вам осталось 300 книг. Начните читать прямо сейчас Вам осталось 300 книг. Начните читать прямо сейчас

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

Esquire
Дым как средство маскировки: как его применяют в армии Дым как средство маскировки: как его применяют в армии

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

Популярная механика
Люди и портреты. Стоит ли злиться на Моргенштерна за слова о Дне победы Люди и портреты. Стоит ли злиться на Моргенштерна за слова о Дне победы

Даже среди патриотов казенщина о Дне Победы вызывает раздражение

СНОБ
Глория Свенсон VS Белла Хадид: как менялись женские стандарты красоты за 100 лет Глория Свенсон VS Белла Хадид: как менялись женские стандарты красоты за 100 лет

Как изменились идеалы красоты со времен золотого века Голливуда?

Cosmopolitan
Карликовая овца Карликовая овца

Порода овец, у которой могучим считается баран, весящий 20 килограммов

Weekend
«Я была проституткой. Надеялась, что меня убьют»: признания звезды шоу «Пацанки» «Я была проституткой. Надеялась, что меня убьют»: признания звезды шоу «Пацанки»

Звезда телешоу «Пацанки» Кристина Зорина занималась проституцией

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

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

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