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

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

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

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

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

Формулировка[править | править вики-текст]

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

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

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

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

История[править | править вики-текст]

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

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

Попытки доказательства[править | править вики-текст]

  • 6 августа 2010 года[7] сотрудник исследовательской лаборатории Hewlett-Packard в Пало-Альто Винэй Деолаликар (англ.) разослал некоторым учёным на проверку своё доказательство неравенства P и NP.[8] Стивен Кук назвал его препринт «относительно серьёзной попыткой решения проблемы P vs NP».[9] Однако уже в том же месяце были найдены недостатки в доказательстве. Деолаликар заявил, что в следующей версии доказательства он постарается учесть все замечания.[7][10] На викистранице «Deolalikar P vs NP paper», связанной с проектом Polymath, приводится критический анализ, собраны предполагаемые ошибки и некоторые опечатки в работе Деолаликара.[11] Там же можно проследить за онлайн-реакцией на предложенное доказательство.
  • Анатолий Панюков в 2013 году сообщил о положительном решении задачи[12]. Результаты были представлены на международных конференциях: Seventh Czech-Slovac International Symposium on Graph Theory, Combinatorics, Algorithms and Applications[13], Третья международная научная конференция Информационные технологии и системы[14], IV International Conference "Mathematical Modelling, Optimization and Information Technologies[15]. Результаты работы также обсуждались на научных семинарах в Институте математики и механики УрО РАН и Института проблем управления РАН. Однако в поданной в 2013 году в журнал «Автоматика и телемеханика» статье была найдена ошибка и статья А. Панюкова не была опубликована.
  • Большой список публикаций, авторы которых заявляют, что доказали или опровергли равенство классов, можно найти на странице Ph.D. Gerhard J Woeginger из технологического университета Эйндховена, Нидерланды.[16]

Защита, предполагающая отсутствие равенства классов P и NP[править | править вики-текст]

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

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

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

Отображение в искусстве[править | править вики-текст]

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

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. А. А. Разборов P ?= NP или проблема перебора: взгляд из 90-х.
  2. А. Х. Шень Проблема перебора // ПостНаука.
  3. Стюарт, 2015, с. 291
  4. Stephen Cook. The Importance of the P versus NP Question.
  5. Л. А. Левин Универсальные задачи перебора (рус.) // Проблемы передачи информации. — 1973. — Т. 9. — № 3. — С. 115—116.
  6. William I. Gasarch (2002). «The P=?NP poll». SIGACT News 33 (2): 34–47. DOI:10.1145/1052796.1052804.
  7. 1 2 Lenta.ru — Мимо
  8. Vinay Deolakikar. P ≠ NP. preprint.
  9. P ≠ NP- Greg and Kat’s blog
  10. The P≠NP «Proof» Is One Week Old
  11. Deolalikar P vs NP paper (англ.). michaelnielsen.org. Проверено 27 августа 2010. Архивировано из первоисточника 1 июня 2012.
  12. Челябинский математик Анатолий Васильевич Панюков: о доказательстве равенства классов P и NP.
  13. A.V. Panyukov Location of a tree for a finite set // Abstracts of the Seventh Czech-Slovac International Symposium on Graph Theory, Combinatorics, Algorithms and Applications. Kosice, Slovakia, 7-13 July 2013. P. 64.
  14. А. В. Панюков. Оптимальное размещение дерева в конечном множестве и полиномиальная разрешимость задач класса NP // Информационные технологии и системы [Электронный ресурс] : тр. Третьей междунар. науч. конф., Банное, Россия, 26 февр.— 2 марта 2014 г. (ИТиС — 2014) : науч. электр. изд. (1 файл 9,9 Мб) / отв. ред. Ю. С. Попков, А. В. Мельников. Челябинск: Изд-во Челяб. гос. ун-та, 2014.
  15. Панюков А. В. Оптимальное размещение вершин дерева в конечном множестве и полиномиальная разрешимость задач класса NP // IV International Conference «Mathematical Modelling, Optimization and Information Technologies» Kishinev, Moldova, March, 2014.
  16. The P-versus-NP page .
  17. Hashcash - A Denial of Service Counter-Measure (2002)

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]