wd wp Пошук: ⬜

Роўнасць класаў P і NP

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

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

Фармулёўка

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

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

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

Гісторыя

З азначэння класаў P і NP адразу атрымліваецца вынік:

P ⊆ N P

{\displaystyle P\subseteq NP}

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

Упершыню пытанне аб роўнасці класаў было пастаўлена Стывенам Кукам у 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]. Там жа можна прасачыць анлайн-рэакцыю на прапанаваны доказ.
Вялікі спіс публікацый, аўтары якіх заяўляюць, што даказалі ці абверглі роўнасць класаў, можна знайсці на старонцы Ph.D. Gerhard J Woeginger з тэхналагічнага ўніверсітэта Эйндхавена, Нідэрланды[8].

Гл. таксама

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

Зноскі

↑ Stephen Cook. The Importance of the P versus NP Question.
↑ William I. Gasarch (2002). “The P=?NP poll”. SIGACT News 33 (2): 34–47. doi:10.1145/1052796.1052804. http://www.cs.umd.edu/~gasarch/papers/poll.pdf.
1 2 Lenta.ru — Мимо
↑ Vinay Deolakikar. P ≠ NP(недаступная спасылка). preprint.
↑ P ≠ NP- Greg and Kat’s blog
↑ The P≠NP «Proof» Is One Week Old
↑ Deolalikar P vs NP paper(англ.) (недаступная спасылка). michaelnielsen.org. Архівавана з першакрыніцы 4 чэрвеня 2014. Праверана 27 жніўня 2010.
↑ The P-versus-NP page .

Спасылкі

С. Кук. Афіцыйнае апісанне праблемы. Архівавана 12 снежня 2010. (англ.)
С. Николенко. «P=?NP» Архівавана 6 чэрвеня 2010.. Компьютерра, 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, некаторыя — адваротнае.