Равенство классов P и NP

Задачи тысячелетия
Равенство классов P и NP
Гипотеза Ходжа
Гипотеза Пуанкаре
Гипотеза Римана
Квантовая теория Янга — Миллса
Существование и гладкость  решений уравнений Навье — Стокса
Гипотеза Бёрча — Свиннертон-Дайера

В теории алгоритмов вопрос о равенстве классов сложности P и NP является одной из центральных открытых проблем уже более трех десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

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

Классы P и NP

В конечном счёте проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)?

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

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

Содержание проблемы

Диаграмма классов сложности при условии P ≠ NP.

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

История

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

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

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

Попытки доказательства

• 6 августа 2010 года^[3] сотрудник исследовательской лаборатории Hewlett-Packard в Пало-Альто Винэй Деолаликар (англ.) разослал некоторым учёным на проверку своё доказательство неравенства P и NP.^[4] Стивен Кук назвал его препринт «относительно серьёзной попыткой решения проблемы P vs NP».^[5] Однако уже в том же месяце были найдены недостатки в доказательстве. Деолаликар заявил, что в следующей версии доказательства он постарается учесть все замечания.^[3][6] На викистранице «Deolalikar P vs NP paper», связанной с проектом Polymath, приводится критический анализ, собраны предполагаемые ошибки и некоторые опечатки в работе Деолаликара.^[7] Там же можно проследить за онлайн-реакцией на предложенное доказательство.

• В 2012 году профессор Восточноукраинского национального университета им. В. Даля, кандидат технических наук Анатолий Плотников опубликовал свой вариант доказательства неравенства P ≠ NP.^[8] По его словам, ранее ему удалось решить эту задачу для частного случая. Текущее решение претендует на общее и в настоящее время проходит проверку^[9].

См. также

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

Примечания

1. ↑ Stephen Cook. The Importance of the P versus NP Question.
2. ↑ William I. Gasarch (2002). «The P=?NP poll». SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804.
3. ↑ ^{1 2} Lenta.ru — Мимо
4. ↑ Vinay Deolakikar. P ≠ NP. preprint.
5. ↑ P ≠ NP- Greg and Kat’s blog
6. ↑ The P≠NP «Proof» Is One Week Old
7. ↑ Deolalikar P vs NP paper  (англ.). michaelnielsen.org. Архивировано из первоисточника 1 июня 2012. Проверено 27 августа 2010.
8. ↑ Anatoly D. Plotnikov. «On the Relationship between Classes P and NP». Journal of Computer Science 8 (7): 1036-1040. DOI:10.3844/jcssp.2012.1036.1040.
9. ↑ Украинский профессор решил одну из семи задач тысячелетия.

Ссылки

• С. Кук Официальное описание проблемы (англ.)
• С. Николенко «P=?NP». Компьютерра, 2006.
• Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография. 2005.
• Притыкин Ю. Л. Что такое проблема P vs. NP? // VIII летняя школа «Современная математика». — Дубна, 2008.
• А. А. Разборов P ?= NP или проблема перебора: взгляд из 90-х.
• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528. — ISBN 0-201-44124-1
• Gerhard J. Woeginger. The P-versus-NP page. (англ.) Список ссылок на предложенные «решения» данной проблемы. Некоторые из них утверждают равенство P и NP, некоторые — обратное.