Просмотр кода страницы Равенство классов P и NP

{{Проблемы тысячелетия}}
Вопрос о '''равенстве [[класс сложности|классов сложности]] [[класс P|''P'']] и [[класс NP|''NP'']]''' (в русских источниках также известный как '''проблема перебора'''<ref>{{статья|автор=А. А. Разборов|заглавие= P ?= NP или проблема перебора: взгляд из 90-х|ссылка=http://www.mi.ras.ru/~razborov/phasis.ps}}</ref><ref>{{статья|автор=[[Шень, Александр Ханиевич|А. Х. Шень]]|заглавие=Проблема перебора |ссылка=http://postnauka.ru/faq/43795 |издание=[[ПостНаука]]}}</ref>) — это одна из центральных открытых проблем [[теория алгоритмов|теории алгоритмов]] уже более трёх десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.

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

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

Аналогичная проблема существует и в [[алгебраическая сложность|теории алгебраической сложности]] для [[Класс VP|классов VP]] и [[Класс VNP|VNP]]{{sfn|Разборов|с=24|2016}}.

== Формулировка ==
[[Файл:Complexity classes.svg|thumb|250px|Диаграмма классов сложности при условии ''P'' ≠ ''NP''.]]

Нестрого говоря, проблема равенства [[Класс P|''P'']] = [[Класс NP|''NP'']] состоит в следующем: если положительный ответ на какой-то вопрос можно довольно быстро ''проверить'' (за [[класс P|полиномиальное время]]), то правда ли, что ответ на этот вопрос можно довольно быстро ''найти'' (также за полиномиальное время и используя [[класс PSPACE|полиномиальную память]])? Другими словами, действительно ли решение задачи проверить не легче, чем его отыскать?{{sfn|Стюарт|2015|с=291}}

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

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

== История ==

Вероятно впервые вопрос о [[Вычислительная сложность|вычислительной сложности]] был задан [[Гёдель, Курт|Куртом Гёделем]] в 1956 году в письме к [[Нейман, Джон фон|Джону фон Нейману]], где он спрашивал, может ли некая задача (которая, как сейчас известно, NP-полная) быть решена за [[Временная сложность алгоритма|квадратичное]] или [[Временная сложность алгоритма|линейное]] время. В то же время Гёдель предположил, что если решение существует, то это позволит решать с помощью компьютеров многие математические проблемы<ref>{{статья |заглавие=Gödel, von Neumann, and the P = NP problem |ссылка=http://ecommons.library.cornell.edu/bitstream/1813/6910/1/89-994.pdf |издание=Bulletin of the European Association for Theoretical Computer Science |том=38 |страницы=101—107 |язык=und |автор=Hartmanis, Juris}}</ref>.

Впервые вопрос о равенстве классов был поставлен [[Кук, Стивен|Стивеном Куком]] в [[1971 год]]у<ref>Stephen Cook. [http://www.cs.toronto.edu/~sacook/homepage/JACMpvsnp.ps The Importance of the P versus NP Question].</ref> и, независимо, [[Левин, Леонид Анатольевич|Леонидом Левиным]] в [[1973 год]]у<ref>{{статья|автор=Л. А. Левин|заглавие=Универсальные задачи перебора |ссылка=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=914&option_lang=rus |язык=ru |издание=Проблемы передачи информации |год=1973 |том=9 |номер=3|страницы=115—116}}</ref>.

На начало 2000-х гг. большинство математиков считают, что эти классы не равны. Согласно опросу, проведённому в [[2002 год]]у среди 100 учёных,<ref>{{статья |заглавие=The P=?NP poll |издание=SIGACT News |том=33 |номер=2 |страницы=34—47 |ссылка=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804 |язык=und |автор=William I. Gasarch |год=2002}}</ref> 61 человек считает, что ответ — «не равны», 9 — «равны», 22 затруднились ответить и 8 считают, что гипотеза не выводима из текущей системы [[аксиома|аксиом]] и, таким образом, не может быть доказана или опровергнута.

Как и другие известные нерешённые математические проблемы, попытки решения этой задачи привлекают значительные усилия; регулярно публикуются (не в научной литературе) ошибочные доказательства равенства или неравенства классов P и NP, обычно непрофессионалами<ref name=fail>[http://lenta.ru/articles/2010/08/18/fail/ Lenta.ru — Мимо. Математики окончательно разуверились в решении задачи тысячелетия]</ref>.

== Системы защиты, предполагающие неравенство классов P и NP ==
{{основная|Односторонняя функция|Криптосистема с открытым ключом|Доказательство выполнения работы}}
Любая [[криптосистема с открытым ключом]] базируется на предположении существования [[односторонняя функция|односторонних функций]] и/или крайней длительности решения некоторой задачи (например, для алгоритма [[RSA]] это разложение на множители очень больших чисел).

Для защиты компьютерных систем от злоупотребления услугами запрашивающей стороне предлагается решить задачу, на поиск решения которой тратится достаточно много времени, а результат легко и быстро проверяется обслуживающей стороной. Примером такой защиты от [[спам]]а может служить система [[Hashcash]]<ref>[ftp://sunsite.icm.edu.pl/site/replay.old/programs/hashcash/hashcash.pdf  Hashcash — A Denial of Service Counter-Measure] (2002)</ref>, которая использует [[хеширование|хеш]] частичной инверсии при отправке электронной почты.

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

== Отображение в искусстве ==
* Во второй серии второго сезона сериала «[[Элементарно]]» описываются потенциальные проблемы, которые могут возникнуть в случае успешного нахождения решения равенства классов P и NP для прикладных случаев.
* Во второй серии первого сезона сериала «Числа» один из главных героев пытался решить эту задачу.
* В сериале «[[Футурама]]» можно заметить папку с заголовком «P=NP».
* В сериале «След» (серия 1358) расследуется убийство профессора, пытавшегося решить проблему равенства классов P и NP.
* В компьютерной игре [[Minecraft]] в главном меню, иногда появляется надпись: «NP is not in P»<ref>[http://minecraft.gamepedia.com/Splash Splash – Official Minecraft Wiki<!-- Заголовок добавлен ботом -->]</ref>.
* В серии книг «Досье Прачечной» [[Стросс, Чарльз|Чарльза Стросса]] якобы последней работой [[Тьюринг, Алан|Алана Тьюринга]] было доказательство равенства классов P и NP. Поскольку это сделало задачи вычислительной магии и демонологии легко решаемыми, его самого убили, замаскировав смерть под самоубийство, а работу засекретили прежде, чем она попала в массовую печать.

== См. также ==
* [[Полный перебор]]
* [[Открытые математические проблемы]]

== Примечания ==
{{примечания|2}}

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

== Ссылки ==
* С. Кук [https://web.archive.org/web/20040613170119/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf Официальное описание проблемы]{{ref-en}}
* С. Николенко [https://web.archive.org/web/20100606064949/http://www2.computerra.ru/xterra/253871/ «P=?NP»]. Компьютерра, 2006.
* Н. П. Варновский. [http://satisfiability.narod.ru/files/www.cryptography.ru-1169817.html Проблема P =? NP, классы сложностей и криптография]. 2005.
* {{статья |автор=Притыкин Ю. Л. |заглавие=Что такое проблема P vs. NP? |издание=VIII летняя школа «Современная математика» |место=Дубна |год=2008 |ссылка=http://www.mccme.ru/dubna/2008/material.htm}}
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page].{{ref-en}} Список ссылок на предложенные «решения» данной проблемы до 2016 года. Некоторые из них утверждают равенство ''P'' и ''NP'', некоторые — обратное.
* Scott Aaronson. [http://www.scottaaronson.com/blog/?p=122 Reasons to believe that P!=NP]
* [[Ааронсон, Скотт|Scott Aaronson]]. [http://www.scottaaronson.com/papers/pnp.pdf <math>{\color{MidnightBlue}\mathsf{P}\stackrel{?}{=}\mathsf{NP}}</math>] — обзор 2017 года.

{{перевести|en|P versus NP problem}}
{{внешние ссылки}}
[[Категория:Классы сложности]]
[[Категория:Математические гипотезы]]
[[Категория:Теория сложности вычислений]]
[[Категория:Нерешённые проблемы информатики]]
[[Категория:Открытые математические проблемы]]
[[Категория:Логические гипотезы]]