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. Kyselyissä suurin osa asiantuntijoista uskoo, että P ei ole yhtä kuin NP, eli PNP. 

 Esimerkki 
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.

 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. 

 Populaarikulttuuri 
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 
 HP boffin claims million-dollar maths prize
Viitteet

 Kirjallisuutta 


Luokka:Ratkaisemattomat matemaattiset ongelmat
Luokka:Seulonnan keskeiset artikkelit