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

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

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

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

Фармулёўка[правіць | правіць зыходнік]

Дыяграма класаў складанасці пры ўмове PNP.

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

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

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

Гісторыя[правіць | правіць зыходнік]

З азначэння класаў P і NP адразу атрымліваецца вынік: 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].

Гл. таксама[правіць | правіць зыходнік]

Зноскі[правіць | правіць зыходнік]

  1. Stephen Cook. The Importance of the P versus NP Question.
  2. 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. 
  3. 3,0 3,1 Lenta.ru — Мимо
  4. Vinay Deolakikar. P ≠ NP. preprint.
  5. P ≠ NP- Greg and Kat’s blog
  6. The P≠NP «Proof» Is One Week Old
  7. Deolalikar P vs NP paper (англ.) . michaelnielsen.org. Архівавана з першакрыніцы 1 чэрвеня 2012. Праверана 27 жніўня 2010.
  8. The P-versus-NP page .

Спасылкі[правіць | правіць зыходнік]