У пытанне аб роўнасці і з'яўляецца адною з цэнтральных адкрытых праблем ужо больш за тры дзесяцігоддзі. Калі на яго будзе станоўчы адказ, гэта будзе азначаць, што тэарэтычна магчыма рашаць многія складаныя задачы істотна скарэй, чым цяпер.

Праблема роўнасці класаў P і NP з'яўляецца адною з сямі , за рашэнне якой назначыў прэмію ў мільён долараў ЗША.

Фармулёўка

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

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

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

Гісторыя

З азначэння класаў P і NP адразу атрымліваецца вынік: . Аднак дагэтуль нічога не вядома аб строгасці гэтага ўключэння, г.зн. ці ёсць у класе NP задача, якая не ляжыць у класе P. Калі такой задачы няма, то ўсе задачы з класа NP можна рашыць за полінаміяльны час, што абяцае велізарную выгаду ў скорасці вылічэнняў. На сёння самыя складаныя задачы з класа NP (так званыя ) можна рашыць за экспаненцыяльны час, што лічыцца непрымальным на практычны погляд.

Упершыню пытанне аб роўнасці класаў было пастаўлена Стывенам Кукам у 1971 годзе і незалежна у 1973 годзеStephen Cook. The Importance of the P versus NP Question..

У цяперашні час большасць матэматыкаў лічыць, што гэтыя класы не роўныя. Згодна з апытаннем, праведзеным у 2002 годзе сярод 100 навукоўцаў, 61 чалавек лічыць, што адказ — «не роўныя», 9 — «роўныя», 22 вагаліся ў адказе і 8 лічаць, што гіпотэза не выводзіцца з цяперашняй сістэмы аксіём і, такім чынам, яе нельга ні даказаць, ні абвергнуць.

Спробы доказу 6 жніўня 2010 года супрацоўнік даследчай лабараторыі Hewlett-Packard у Пала-Альта разаслаў некаторым вучоным на праверку свой доказ няроўнасці P і NP Vinay Deolakikar. P ≠ NP. preprint.. Стывен Кук назваў яго прэпрынт «адносна сур'ёзнаю спробаю рашэння праблемы P vs NP»P ≠ NP- Greg and Kat’s blog. Аднак ужо ў тым жа месяцы былі знойдзены недахопы ў доказе. Дэалалікар заявіў, што ў наступнай версіі доказу ён пастараецца ўлічыць усе заўвагіLenta.ru — МимоThe P≠NP «Proof» Is One Week Old. На вікістаронцы «Deolalikar P vs NP paper», звязанай з праектам Polymath, прыводзіцца крытычны аналіз, сабраныя меркаваныя памылкі і некаторыя апіскі ў рабоце Дэалалікара. Там жа можна прасачыць анлайн-рэакцыю на прапанаваны доказ. Вялікі спіс публікацый, аўтары якіх заяўляюць, што даказалі ці абверглі роўнасць класаў, можна знайсці на старонцы Ph.D. Gerhard J Woeginger з тэхналагічнага ўніверсітэта Эйндхавена, НідэрландыThe P-versus-NP page ..

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

Зноскі

Спасылкі С. Кук. Афіцыйнае апісанне праблемы. С. Николенко. «P=?NP» . Компьютерра, 2006. Н. П. Варновский. Проблема P =? NP, классы сложностей и криптография. 2005.

А. А. Разборов. P ?= NP или проблема перебора: взгляд из 90-х .

Gerhard J. Woeginger. The P-versus-NP page. Спіс спасылак на прапанаваныя «рашэнні» данай праблемы. Некаторыя з іх сцвярджаюць роўнасць P і NP, некаторыя — адваротнае.

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