Рассказываем о неравенстве 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
Театр луны Театр луны

Певица Кристина Луна рассказала об ощущении возраста и ностальгии по 90-м

Grazia
Почему уличные фонари в основном излучают желтый и оранжевый свет? Почему уличные фонари в основном излучают желтый и оранжевый свет?

Почему цвет фонарей на улицах не меняют уже столько лет?

ТехИнсайдер
Стыд и спам Стыд и спам

История спама — от банки посредственной ветчины до многомиллионных махинаций

GQ
Целибат сведет в могилу: почему не заниматься сексом смертельно опасно Целибат сведет в могилу: почему не заниматься сексом смертельно опасно

Наука в очередной раз доказала, что секс — это лучшее лекарство

Maxim
Опера — это весело? Какие постановки заставляли публику смеяться Опера — это весело? Какие постановки заставляли публику смеяться

Почему опера — это весело

РБК
Пять космических туристов, слетавших в космос веселья ради Пять космических туристов, слетавших в космос веселья ради

Пять космических туристов, проложивших тропу к космодромам

Maxim
Орбитальное движение глюонов не повлияло на излучение от столкновений протонов Орбитальное движение глюонов не повлияло на излучение от столкновений протонов

Картина об устройстве протона постепенно проясняется

N+1
Моделирование подтвердило образование тяжелых элементов в столкновениях нейтронных звезд Моделирование подтвердило образование тяжелых элементов в столкновениях нейтронных звезд

Источник тяжелых элементов во Вселенной — столкновение нейтронных звезд

N+1
В Австрии нашли древнюю золотую чашу с солярной символикой В Австрии нашли древнюю золотую чашу с солярной символикой

Редкому артефакту урнопольской культуры оказалось более 3000 лет

N+1
Искусство убеждать: 14 правил ведения сложных переговоров Искусство убеждать: 14 правил ведения сложных переговоров

Отрывок из книги «Убедить дракона» — об особенностях ведения переговоров

Inc.
Автобудущее Автобудущее

Мы находимся на пороге одних из самых быстрых перемен в работе транспорта

Популярная механика
Гидрофойл для миллионов Гидрофойл для миллионов

Гидрофойл – доска на подводных крыльях для серфинга

Популярная механика
Малый Эрмитаж Малый Эрмитаж

Висячий сад и часы «Павлин»

Культура.РФ
6 советов тем, кто ищет счастья 6 советов тем, кто ищет счастья

Как быть счастливым даже в непростой жизненный период?

Psychologies
Умер легендарный лыжник Вячеслав Веденин, тот самый, кто придумал слово «дахусим» и не опустил флаг СССР перед императором Японии Умер легендарный лыжник Вячеслав Веденин, тот самый, кто придумал слово «дахусим» и не опустил флаг СССР перед императором Японии

Вячеслав Веденин. Легенда СССР, который показал характер на Олимпиаде 1972

Maxim
Круглые черви покормили личинок желточным молоком Круглые черви покормили личинок желточным молоком

Биологи обнаружили у нематод аналог грудного молока

N+1
Молодо — зелено Молодо — зелено

Каково влияние ESG-трендов на жизнь людей сегодня и завтра

РБК

Женщина, которая хочет в общей сложности родить 17 раз

Cosmopolitan
10 поз, в которых спит твой кот, и что они значат 10 поз, в которых спит твой кот, и что они значат

Оказывается, по тому, как спит кот, можно понять его загадочную душу!

Maxim
Покажи язык Покажи язык

Как лингвисты доказывали, что жестовые языки — это языки

N+1
Хозяин тайги Хозяин тайги

Как иркутский миллиардер Николай Буйнов добывает нефть и газ в сибирской глуши

Forbes
Хозяйка Хозяина: как крестьянка Валя Истомина стала последней любовницей Сталина Хозяйка Хозяина: как крестьянка Валя Истомина стала последней любовницей Сталина

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

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

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

Playboy
Все о матери Все о матери

Пенелопа Крус — об опыте материнства и традиционных ценностях

Glamour
«Обязательный завтрак, вредный кофе и опасный фастфуд. Почему  почти все, что нам рассказывали о еде, неправда» «Обязательный завтрак, вредный кофе и опасный фастфуд. Почему  почти все, что нам рассказывали о еде, неправда»

Насколько популярные утверждения о еде иногда далеки от правды

N+1
Игра в ассоциации Игра в ассоциации

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

SALON-Interior
Обложки трудной судьбы Обложки трудной судьбы

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

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

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

РБК
Поселившийся в аду Орфей. Как Георгий Иванов из любимца муз и бонвивана стал самым глубоким и печальным поэтом русской эмиграции Поселившийся в аду Орфей. Как Георгий Иванов из любимца муз и бонвивана стал самым глубоким и печальным поэтом русской эмиграции

Его называли «первым поэтом русской эмиграции», а еще «ничтожным эпигоном»

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