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.

Lähteet 
 HP boffin claims million-dollar maths prize

Viitteet

Kirjallisuutta 
 

Ratkaisemattomat matemaattiset ongelmat
Seulonnan keskeiset artikkelit