P=NP
Wikipedia
Laskennan vaativuusteoriassa lasketaan eri ongelmien laskemiseen tarvittavia laskentaresursseja. Yleisimmät näistä resursseista ovat aika ja muisti. Luokkaan P (polynomial) kuuluvat kaikki ongelmat, jotka voidaan ratkaista tehokkaasti. Luokkaan NP (non-deterministic polynomial) taas kuuluvat ongelmat joiden ratkaisun oikeellisuus voidaan verifioida tehokkaasti. Määritelmän perusteella P ⊆ NP.
Vaativuusteorian kuuluisimpiin ongelmiin kuuluu näiden kahden luokan välinen suhde eli onko P = NP?
Clay-instituutti on luvannut miljoona dollaria tämän ongelman ratkaisusta.
P = NP ongelman voi ilmaista myös näin: "Jos jonkun ongelman ratkaisun voi verifioida tehokkaasti, niin voidaanko ongelma myös ratkaista tehokkaasti?"