Problemet med klassene P og NP er fortsatt et åpent problem i beregningskompleksitetsteorien .
Selv om det er en millionpremie på spill, er problemet fortsatt uten en løsning (det er et av årtusenets problemer ).
På et uformelt nivå krever det å avgjøre om ethvert problem som en datamaskin er i stand til å verifisere riktigheten av en positiv løsning for, på en akseptabel tid, også er et problem som kan løses av datamaskinen på en akseptabel tid (det vil si , hvis datamaskinen er i stand til å finne en positiv løsning på egen hånd på en akseptabel tid).
Hvis svaret er nei , er det problemer som det er vanskeligere å beregne en bestemt løsning for enn å verifisere den.
En formell definisjon bruker kompleksitetsklassene P og NP . Den første består av alle de beslutningsproblemene som kan løses med en deterministisk Turing-maskin i en tid som er polynom med hensyn til størrelsen på inngangsdataene; den andre består av alle de beslutningsproblemene hvis positive løsninger kan verifiseres i polynomisk tid med riktig informasjon, eller, tilsvarende, hvis løsning kan finnes i polynomisk tid med en ikke-deterministisk Turing-maskin . Problemet med klassene P og NP er derfor løst i følgende spørsmål:
Er P lik NP ?Et eksempel for å få en ide om hva dette betyr. Anta at vi ønsker å beregne alle divisorene (heltallsdivisjon, det vil si med resten lik null) til et tall n . Problemet er da å finne alle tallene x slik at x er en divisor av n .
Det er lett nok å verifisere at et visst tall x 0 er en divisor av n ; det er tilstrekkelig å utføre divisjonsoperasjonen og kontrollere resten: hvis det er lik null, er tallet en divisor, ellers er det ikke. Antallet trinn som kreves for å utføre delingsoperasjonen er større jo større tallet n er, men det er alltid raskt nok til at tiden som kreves, anses som akseptabel .
Motsatt er det kanskje ikke like lett å bestemme settet med alle divisorer. Faktisk krever nesten alle metodene [1] som er utviklet gjennom århundrene en tid som øker raskt når verdien av n øker , for mye til at det kan anses som akseptabelt .
En viktig rolle i denne diskusjonen spilles av settet med NP-komplette problemer, [1] som intuitivt kan beskrives som de problemene som helt sikkert ikke ville tilhørt P hvis P var forskjellig fra NP . Tvert imot, ved å bevise at selv for et enkelt NP-komplett problem at det tilhører P , vil vi få et bevis på at P og NP er likeverdige. På en måte er NP-komplette problemer de som minst sannsynlig tilhører P også .