Прагляд зыходнага тэксту старонкі Роўнасць класаў P і NP

{{Праблемы тысячагоддзя}}
У {{нп5|тэорыя алгарытмаў|тэорыі алгарытмаў|ru|Теория алгоритмов}} пытанне аб '''роўнасці {{нп5|клас складанасці|класаў складанасці|ru|Класс сложности}} {{нп5|клас P|''P''|ru|Класс P}} і {{нп5|клас NP|''NP''|ru|Класс NP}}''' з'яўляецца адною з цэнтральных адкрытых праблем ужо больш за тры дзесяцігоддзі. Калі на яго будзе станоўчы адказ, гэта будзе азначаць, што тэарэтычна магчыма рашаць многія складаныя задачы істотна скарэй, чым цяпер.

Праблема роўнасці класаў ''P'' і ''NP'' з'яўляецца адною з сямі {{нп5|задачы тысячагоддзя|задач тысячагоддзя|ru|Задачи тысячелетия}}, за рашэнне якой {{нп3|Матэматычны інстытут Клэя||ru|Математический институт Клэя}} назначыў прэмію ў мільён [[долар ЗША|долараў ЗША]].

== Фармулёўка ==
[[Файл:Complexity classes.svg|thumb|250px|Дыяграма класаў складанасці пры ўмове ''P'' ≠ ''NP''.]]

Нястрога кажучы, праблема роўнасці [[Клас P|''P'']] = [[Клас NP|''NP'']] заключаецца ў наступным: калі станоўчы адказ на нейкае пытанне можна хутка ''праверыць'' (за полінаміяльны час), то ці праўда, што адказ на гэтае пытанне можна быстра ''знайсці'' (за [[клас P|полінаміяльны час]], выкарыстоўваючы {{нп5|клас PSPACE|полінаміяльную памяць|ru|Класс PSPACE}})?
Іншымі словамі, ці праўда, што рашэнне задачы праверыць не лягчэй, чым яго адшукаць?

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

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

== Гісторыя ==

З азначэння класаў [[Клас P|''P'']] і [[Клас NP|''NP'']] адразу атрымліваецца вынік: <math>P \subseteq NP</math>. Аднак дагэтуль нічога не вядома аб строгасці гэтага ўключэння, г.зн. ці ёсць у класе ''NP'' задача, якая не ляжыць у класе ''P''. Калі такой задачы няма, то ўсе задачы з класа ''NP'' можна рашыць за полінаміяльны час, што абяцае велізарную выгаду ў скорасці вылічэнняў. На сёння самыя складаныя задачы з класа ''NP'' (так званыя {{нп5|NP-поўная задача|''NP''-поўныя задачы|ru|NP-полная задача}}) можна рашыць за экспаненцыяльны час, што лічыцца непрымальным на практычны погляд.

Упершыню пытанне аб роўнасці класаў было пастаўлена [[Стывен Артур Кук|Стывенам Кукам]] у 1971 годзе і незалежна {{нп3|Леанід Анатольевіч Левін|Леанідам Левіным|ru|Левин, Леонид Анатольевич}} у 1973 годзе<ref>Stephen Cook. [http://www.cs.toronto.edu/~sacook/homepage/JACMpvsnp.ps The Importance of the P versus NP Question].</ref>.

У цяперашні час большасць матэматыкаў лічыць, што гэтыя класы не роўныя. Згодна з апытаннем, праведзеным у 2002 годзе сярод 100 навукоўцаў<ref>{{cite journal|author=William I. Gasarch|title=The P=?NP poll |journal=SIGACT News |volume=33 |issue=2 |pages=34–47 |year=2002 |url=http://www.cs.umd.edu/~gasarch/papers/poll.pdf |doi=10.1145/1052796.1052804}}</ref>, 61 чалавек лічыць, што адказ — «не роўныя», 9 — «роўныя», 22 вагаліся ў адказе і 8 лічаць, што гіпотэза не выводзіцца з цяперашняй сістэмы [[аксіёма|аксіём]] і, такім чынам, яе нельга ні даказаць, ні абвергнуць.

== Спробы доказу ==
* 6 жніўня 2010 года<ref name=fail/> супрацоўнік даследчай лабараторыі [[Hewlett-Packard]] у [[Пала-Альта]] {{не перакладзена|Вінэй Дэалалікар||en|Vinay Deolalikar}} разаслаў некаторым вучоным на праверку свой доказ няроўнасці P і NP <ref>Vinay Deolakikar. [http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp12pt.pdf P ≠ NP]{{Недаступная спасылка}}. preprint.</ref>. [[Стывен Артур Кук|Стывен Кук]] назваў яго [[прэпрынт]] «адносна сур'ёзнаю спробаю рашэння праблемы P vs NP»<ref>[http://gregbaker.ca/blog/2010/08/07/p-n-np/ P ≠ NP- Greg and Kat’s blog<!-- Заголовок добавлен ботом -->]</ref>. Аднак ужо ў тым жа месяцы былі знойдзены недахопы ў доказе. Дэалалікар заявіў, што ў наступнай версіі доказу ён пастараецца ўлічыць усе заўвагі<ref name=fail>[http://lenta.ru/articles/2010/08/18/fail/ Lenta.ru — Мимо]</ref><ref>[http://rjlipton.wordpress.com/2010/08/15/the-p≠np-proof-is-one-week-old/ The P≠NP «Proof» Is One Week Old]</ref>. На вікістаронцы «Deolalikar P vs NP paper», звязанай з праектам Polymath, прыводзіцца крытычны аналіз, сабраныя меркаваныя памылкі і некаторыя апіскі ў рабоце Дэалалікара<ref>{{cite web|url=http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper|title=Deolalikar P vs NP paper|publisher=michaelnielsen.org|lang=en|accessdate=2010-08-27|archiveurl=https://web.archive.org/web/20140604011256/http://michaelnielsen.org/polymath1/index.php?title=Deolalikar_P_vs_NP_paper|archivedate=4 чэрвеня 2014|url-status=dead}}</ref>. Там жа можна прасачыць анлайн-рэакцыю на прапанаваны доказ.
* Вялікі спіс публікацый, аўтары якіх заяўляюць, што даказалі ці абверглі роўнасць класаў, можна знайсці на старонцы Ph.D. Gerhard J Woeginger з тэхналагічнага ўніверсітэта Эйндхавена, Нідэрланды<ref>[http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page ].</ref>.

== Гл. таксама ==
* [[Адкрытыя матэматычныя праблемы]]

== Зноскі ==
{{reflist|2}}

== Спасылкі ==
* С. Кук. [http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf Афіцыйнае апісанне праблемы.] {{Архівавана|url=https://web.archive.org/web/20101212035424/http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf |date=12 снежня 2010 }} {{ref-en}}
* С. Николенко. [http://www2.computerra.ru/xterra/253871/ «P=?NP»] {{Архівавана|url=https://web.archive.org/web/20100606064949/http://www2.computerra.ru/xterra/253871/ |date=6 чэрвеня 2010 }}. Компьютерра, 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}}
* А. А. Разборов. [http://www.mi.ras.ru/~razborov/phasis.ps P ?= NP или проблема перебора: взгляд из 90-х].
* {{кніга
|загаловак = Введение в теорию автоматов, языков и вычислений
|арыгінал = Introduction to Automata Theory, Languages, and Computation
|аўтар = Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман
|спасылка = 
|isbn = 0-201-44124-1
|старонкі = 528
|год = 2002
|выданне = 
|месца =  М.
|выдавецтва = «Вильямс»
}}
* Gerhard J. Woeginger. [http://www.win.tue.nl/~gwoegi/P-versus-NP.htm The P-versus-NP page.] {{ref-en}} Спіс спасылак на прапанаваныя «рашэнні» данай праблемы. Некаторыя з іх сцвярджаюць роўнасць ''P'' і ''NP'', некаторыя — адваротнае.

[[Катэгорыя:Класы складанасці]]
[[Катэгорыя:Матэматычныя гіпотэзы]]
[[Катэгорыя:Тэорыя складанасці вылічэнняў]]
[[Катэгорыя:Нярэшаныя праблемы інфарматыкі]]
[[Катэгорыя:Адкрытыя матэматычныя праблемы]]
[[Катэгорыя:Лагічныя гіпотэзы]]