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.
Dægurmenning
[breyta | breyta frumkóða]Kvikmyndin Traveling Salesman frá árinu 2012 fjallar um fjóra stærðfræðinga sem bandaríska ríkisstjórnin ræður til að leysa P vs NP vandamálið.[2]
Í sjöundu þáttaröð The Simpsons-fjölskyldunnar, í sjötta þættinum „Treehouse of Horror VI“, sést jafnan P=NP stuttu eftir að Homer lendir óvart í „þriðju víddinni“.[3]
Í annarri þáttaröð Elementary, í öðrum þættinum „Solve for X“, snýst söguþráðurinn um Sherlock og Watson sem rannsaka morð á stærðfræðingum sem voru að reyna að leysa P vs NP.[4]
Í teiknimyndasögunni The Phantom Researcher eftir Robin Cousin fullyrðir týndur rannsakandi að hafa leyst P ≟ NP.[5]
Í skáldsögunni The Ruby Circuit eftir Martin G. Ljungqvist snýst söguþráðurinn um stærðfræðinga og P vs NP vandamálið.[6][7]
Tilvísanir
[breyta | breyta frumkóða]- 1 2 „Hvað felst í vandamálinu ,,P vs. NP?“. Vísindavefurinn.
- ↑ Geere, Duncan. „Film explores moral and political repercussions of proving P equals NP“. Wired (bandarísk enska). ISSN 1059-1028. Sótt 19 apríl 2026.
- ↑ Hardesty, Larry (29 október 2009). „Explained: P vs. NP“. MIT News | Massachusetts Institute of Technology (enska). Sótt 19 apríl 2026.
- ↑ Gasarch, Bill. „P vs NP is Elementary? No-- P vs NP is ON Elementary“ (enska). Sótt 19 apríl 2026.
- ↑ Kakalios, James (24 febrúar 2023). „Graphic novel tells a tale of catastrophe and complexity“. Physics World (bresk enska). Sótt 19 apríl 2026.
- ↑ Virgin, Karin (22 janúar 2021). „Han har skrivit en spänningsroman om matematik“. Ingenjören (sænska). Sótt 19 apríl 2026.
- ↑ Hallonsten, Anna-Karin. „Han gör spänningsroman – om matteproblem“. Ämnesläraren – matematik, NO, teknik (sænska). Sótt 19 apríl 2026.