P vs. NP vandamálið
P vs. NP (eða, er P = NP?) er eitt mikilvægasta opna (óleysta) 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ð).
Ef P ≠ NP, eins og flestir telja, þýðir það að vandamál í NP eru erfiðari að reikna en að staðfesta.
Vandamálið hefur verið kallað mikilvægasta opna vandamálið í (fræðilegri) tölvunarfræði.
Það er eitt a sjö Millennium Prize Problems, þ.e. vandamálum sem Clay Mathematics Institute valdi, og verðlaunin eru milljón Bandaríkjadollarar fyrir svar á spurningunni „er P = NP?“ hvort sem svarið er já eða nei, ef hægt er að sýna fram á að annað hvort sé rétt lausn.
Dæmi
[breyta | breyta frumkóða]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.