P=NP-vandamálið

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita

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[breyta]

  1. 1,0 1,1 Vísindavefurinn:Hvað felst í vandamálinu ,,P vs. NP?