![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Complexity_classes.svg/langfi-640px-Complexity_classes.svg.png&w=640&q=50)
P=NP
ratkaisematon ongelma tietojenkäsittelytieteessä / From Wikipedia, the free encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/Complexity_classes.svg/320px-Complexity_classes.svg.png)
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]