WikiSort.ru - Не сортированное

Вопрос о равенстве классов сложности P и NP (в русских источниках также известный как проблема перебора^[1][2]) — это одна из центральных открытых проблем теории алгоритмов уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

Отношения между классами P и NP рассматриваются в разделе теории алгоритмов, который называется теорией вычислительной сложности. Она изучает ресурсы, необходимые для решения некоторой задачи. Наиболее общие ресурсы — это время (сколько нужно сделать шагов) и память (сколько памяти потребуется для решения задачи).

Проблема равенства классов P и NP является одной из семи задач тысячелетия, за решение которой Математический институт Клэя назначил премию в миллион долларов США.

Аналогичная проблема существует и в теории алгебраической сложности для классов VP и VNP^[3].

Формулировка

Нестрого говоря, проблема равенства P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно довольно быстро найти (также за полиномиальное время и используя полиномиальную память)? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?^[4]

Например, верно ли, что среди чисел {−2, −3, 15, 14, 7, −10, …} есть такие, что их сумма равна 0 (задача о суммах подмножеств)? Ответ — да, потому что −2 −3 + 15 −10 = 0 легко проверяется несколькими сложениями (информация, необходимая для проверки положительного ответа, называется сертификатом). Следует ли отсюда, что так же легко подобрать эти числа? Проверить сертификат так же легко, как найти его? Кажется, что подобрать числа сложнее, но это не доказано.

Из определения классов P и NP сразу вытекает следствие: ${\displaystyle P\subseteq NP}$ . Однако до сих пор ничего не известно о строгости этого включения, то есть, существует ли задача, лежащая в NP, но не лежащая в P. Если такой задачи не существует, то все задачи, принадлежащие классу NP, можно будет решать за полиномиальное время, что сулит огромную выгоду в скорости вычислений. Сейчас самые сложные задачи из класса NP (так называемые NP-полные задачи) можно решить за экспоненциальное время, что считается неприемлемым с практической точки зрения.

История

Вероятно впервые вопрос о вычислительной сложности был задан Куртом Гёделем в 1956 году в письме к Джону фон Нейману, где он спрашивал, может ли некая задача (которая, как сейчас известно, NP-полная) быть решена за квадратичное или линейное время. В то же время Гёдель предположил, что если решение существует, то это позволит решать с помощью компьютеров многие математические проблемы^[5].

Впервые вопрос о равенстве классов был поставлен Стивеном Куком в 1971 году^[6] и, независимо, Леонидом Левиным в 1973 году^[7].

На начало 2000-х гг. большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в 2002 году среди 100 учёных,^[8] 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы аксиом и, таким образом, не может быть доказана или опровергнута.

Как и другие известные нерешённые математические проблемы, попытки решения этой задачи привлекают значительные усилия; регулярно публикуются (не в научной литературе) ошибочные доказательства равенства или неравенства классов P и NP, обычно непрофессионалами^[9].

Системы защиты, предполагающие неравенство классов P и NP

Любая криптосистема с открытым ключом базируется на предположении существования односторонних функций и/или крайней длительности решения некоторой задачи (например, для алгоритма RSA это разложение на множители очень больших чисел).

Для защиты компьютерных систем от злоупотребления услугами запрашивающей стороне предлагается решить задачу, на поиск решения которой тратится достаточно много времени, а результат легко и быстро проверяется обслуживающей стороной. Примером такой защиты от спама может служить система Hashcash^[10], которая использует хеш частичной инверсии при отправке электронной почты.

В блокчейнах, основанных на технологии доказательста выполнения работы требуется, чтобы получаемая хеш-сумма была меньше целевого значения. Процесс поиска нужной хеш-суммы требует её многократного пересчёта с перебором произвольных значений дополнительного параметра (подробнее см. Майнинг). На поиск одной удовлетворительной хеш-суммы все компьютеры системы тратят значительное время (например, в «Биткойн» это в среднем 10 минут). Для проверки корректности уже сформированного блока требуется лишь однократное вычисление хеша.

Отображение в искусстве

• Во второй серии второго сезона сериала «Элементарно» описываются потенциальные проблемы, которые могут возникнуть в случае успешного нахождения решения равенства классов P и NP для прикладных случаев.
• Во второй серии первого сезона сериала «Числа» один из главных героев пытался решить эту задачу.
• В сериале «Футурама» можно заметить папку с заголовком «P=NP».
• В сериале «След» (серия 1358) расследуется убийство профессора, пытавшегося решить проблему равенства классов P и NP.
• В компьютерной игре Minecraft в главном меню, иногда появляется надпись: «NP is not in P»^[11].
• В серии книг «Досье Прачечной» Чарльза Стросса якобы последней работой Алана Тьюринга было доказательство равенства классов P и NP. Поскольку это сделало задачи вычислительной магии и демонологии легко решаемыми, его самого убили, замаскировав смерть под самоубийство, а работу засекретили прежде, чем она попала в массовую печать.

См. также

• Полный перебор
• Открытые математические проблемы

Примечания

Литература

• Иэн Стюарт. Величайшие математические задачи. — М.: Альпина нон-фикшн, 2015. — 460 с. — ISBN 978-5-91671-318-3.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман. Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — 528 с. — ISBN 0-201-44124-1.
• Разборов А. А. Алгебраическая сложность. — М.: МЦНМО, 2016. — 32 с. — ISBN 978-5-4439-1032-1.

Ссылки

• С. Кук Официальное описание проблемы (англ.)
• С. Николенко «P=?NP». Компьютерра, 2006.
• Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография. 2005.
• Притыкин Ю. Л. Что такое проблема P vs. NP? // VIII летняя школа «Современная математика». — Дубна, 2008.
• Gerhard J. Woeginger. The P-versus-NP page. (англ.) Список ссылок на предложенные «решения» данной проблемы до 2016 года. Некоторые из них утверждают равенство P и NP, некоторые — обратное.
• Scott Aaronson. Reasons to believe that P!=NP
• Scott Aaronson. ${\displaystyle {\color {MidnightBlue}{\mathsf {P}}{\stackrel {?}{=}}{\mathsf {NP}}}}$ — обзор 2017 года.