„P vs. NP vandamálið“: Munur á milli breytinga

Efni eytt Efni bætt við

Innfellt

Útgáfa síðunnar 2. nóvember 2012 kl. 01:46

P=NP-vandamálið er eitt mikilvægasta opna vandamál innan tölvunarfræðinnar,^[1] sem spyr óformlega hvort það sé auðvelt fyrir tölvur að leysa þau vandamál sem er auðvelt að staðfesta svarið á. Vandamálið var kynnt til sögunnar árið 1971 af Stephen Cook.

Ákveðið vandamál tilheyrir flækjustigsflokkinum P ef hægt er að leysa það auðveldlega og það tilheyrir flækjustigsflokkinum NP ef hægt er að staðfesta uppgefna lausn auðveldlega^[1] (þar sem auðvelt er óformlega notað þegar fjölda aðgerða er af margliðustærðargráðu miðað við inntakið).

Hlutasummuvandamálið (e. subset sum problem) er dæmi um vandamál þar sem það er auðvelt að staðfesta uppgefna lausn en mögulega erfitt að finna lausn. Er til dæmis einhver hlutmengi {−2, −3, 15, 14, 7, −10} sem hefur summuna 0? Hægt er að staðfesta lausnina {−2, −3, −10, 15} auðveldlega með þremur samlagningum, en það er ekkert þekkt reiknirit sem finnur slíkt hlutmengi sem er í P: slíkt reiknirit getur aðeins verið til ef P = NP.

Tilvísanir

↑ ^1,0 ^1,1 „Hvað felst í vandamálinu ,,P vs. NP?“. Vísindavefurinn.

[vis-1] 1,0 ^1,1 „Hvað felst í vandamálinu ,,P vs. NP?“. Vísindavefurinn.

[1]

@@ Lína 11: / Lína 11: @@
 [[ar:مسألة P=NP]]
+[[az:P=NP]]
 [[ca:P versus NP]]
 [[cs:Problém P versus NP]]
 [[de:P-NP-Problem]]
 [[en:P versus NP problem]]
-[[es:Clases de complejidad P y NP]]
 [[eo:Demando P = NP]]
+[[es:Clases de complejidad P y NP]]
 [[fa:مسئله برابری پی و ان‌پی]]
+[[fi:P=NP]]
 [[fr:Problème P = NP]]
-[[ko:P-NP 문제]]
 [[it:Classi di complessità P e NP]]
 [[ja:P≠NP予想]]
+[[ko:P-NP 문제]]
 [[pt:P versus NP]]
 [[ru:Равенство классов P и NP]]
 [[simple:P versus NP]]
 [[sr:П = НП проблем]]
-[[fi:P=NP]]
 [[sv:P=NP?]]
 [[th:กลุ่มความซับซ้อน พี และ เอ็นพี]]