P=NP
P=NP? on laskennan vaativuusteorian kuuluisimpia ratkaisemattomia ongelmia. Ongelmassa yritetään ratkaista vaativuusluokkien P ja NP suhdetta. P=NP -ongelma voidaan ilmaista epämuodollisesti seuraavasti: ”Jos jonkin ongelman ratkaisu voidaan tarkastaa tehokkaasti, niin voidaanko ongelma myös ratkaista tehokkaasti?”. P=NP -ongelma on yksi Clay-instituutin seitsemästä Millennium-ongelmasta, joiden ratkaisijoille on luvassa miljoona dollaria.
Luokkaan P (polynomial) kuuluvat kaikki ongelmat, jotka tiedetään voitavan ratkaista "tehokkaasti" eli polynomisessa ajassa. Toisin sanoen ratkaisuun kuuluva aika voidaan ilmaista polynomina ongelman koon suhteen. Luokkaan NP (non-deterministic polynomial) taas kuuluvat ongelmat, joiden ratkaisun oikeellisuus voidaan tarkastaa tehokkaasti. Määritelmän perusteella P ⊆ NP, eli kaikki P-ongelmat ovat myös NP-ongelmia. Jos P=NP on totta, niin se tarkoittaisi sitä, että myös kaikki NP-ongelmat olisivat P-ongelmia, eli P- ja NP-ongelmat olisivat täsmälleen samat.[1] Kyselyissä suurin osa asiantuntijoista uskoo, että P ei ole yhtä kuin NP, eli PNP.[2]
Esimerkki
[muokkaa | muokkaa wikitekstiä]Esimerkki NP-ongelmasta on sudokun ratkaistavuusongelma: löytyykö annettuun sudokuruudukkoon sudokun sääntöjen mukainen ratkaisu? Minkä tahansa ehdotetun ratkaisun oikeellisuus voidaan tarkastaa nopeasti eli polynomisessa ajassa. Jos kuitenkin tarkastellaan sudokuruudukkoa, joka voi olla kuinka iso tahansa, ratkaisun löytämisaika kasvaa eksponentiaalisesti eli paljon nopeammin kuin ratkaisun tarkistamiseen kuuluva polynominen aika. Siispä sudoku on nopeasti tarkistettavissa, mutta ei nopeasti ratkaistavissa. Jos P=NP pitää paikkansa, olisi sudokun ratkaisemiseen olemassa algoritmi, jossa ongelman koko vaikuttaisi ratkaisuaikaan paljon nykyisin tunnettuja menetelmiä vähemmän.[3]
NP-täydellisyys
[muokkaa | muokkaa wikitekstiä]- Pääartikkeli: NP-täydellisyys
NP-täydelliseksi kutsutaan sellaista NP-luokan ongelmaa, jolle polynomisessa ajassa toimivan ratkaisun löytyminen merkitsisi sitä, että kaikkiin luokan NP-ongelmiin löytyisi polynomisessa ajassa toimiva ratkaisu. Siispä yhden NP-täydellisen ongelman ratkaiseminen polynomisessa ajassa tarkoittaisi suoraan, että P=NP pitää paikkansa. NP-täydellisiin ongelmiin kuuluu mm. kauppamatkustajan ongelma ja lukuisia muita tärkeitä ongelmia. Nykyisin kaikki tunnetut NP-täydellisten ongelmien ratkaisualgoritmit ovat ylipolynomisia, eli niiden vaativuus kasvaa erittäin nopeasti ongelman suuruusluokan kasvaessa.[1]
Populaarikulttuuri
[muokkaa | muokkaa wikitekstiä]Vuoden 2012 elokuva Travelling Salesman on tarina neljästä matemaatikosta, jotka Yhdysvaltain hallitus palkkasi ratkaisemaan P vs NP -ongelman.
Simpsonien seitsemännen kauden kuudennessa jaksossa nimeltä "Treehouse of Horror VI" yhtälö P=NP nähdään pian sen jälkeen, kun Homer vahingossa kompastui "kolmannelle ulottuvuudelle".
Holmes NYC-sarjan toisen kauden toisen jakson "Solve for X" juoni pyörii Sherlockin ja Watsonin ympärillä, jotka tutkivat matemaatikoiden murhia, jotka yrittivät ratkaista P vs NP -ongelman.
Martin G. Ljungqvistin romaanissa Rubinkretsen juoni pyörii matemaatikoiden ja P vs NP -ongelman ympärillä.
Lähteet
[muokkaa | muokkaa wikitekstiä]Viitteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b Orponen, Pekka: "P = NP" -ongelma ja laskennan vaativuusteoria 1.1.2007. Aalto-yliopisto. Viitattu 15.1.2022.
- ↑ Gasarch, William: Guest Column: The Second P =? NP Poll SIGACT News. 2012. Viitattu 15.1.2022. (englanniksi)
- ↑ Eliran Natan: P vs. NP — What Is The Difference Between Solving A Problem And Recognizing Its Solution? Medium. 8.4.2021. Viitattu 15.1.2022. (englanniksi)
Kirjallisuutta
[muokkaa | muokkaa wikitekstiä]- Fortnow, Lance: Kultainen pääsylippu: P, NP ja mahdottoman tavoittelu. ((The Golden Ticket: P, NP, and the Search for the Impossible, 2013.) Suomentanut Kimmo Pietiläinen) Helsinki: Terra cognita, 2014. ISBN 978-952-5697-69-8