Antag, at du organiserer boliger til en gruppe på fire hundrede universitetsstuderende. Pladsen er begrænset, og kun hundrede af de studerende vil modtage pladser i sovesalen. At komplicere sager, dekanen har givet dig en liste over par inkompatible studerende, og anmodede om, at der ikke vises noget par fra denne liste i dit endelige valg., Dette er et eksempel på, hvad dataloger kalde en NP-problem, da det er let at kontrollere, om et givet valg af hundrede studerende, der er foreslået af en medarbejder er tilfredsstillende (dvs, uden par, taget fra din kollega”s liste, vises også på listen fra Dean”s kontor), men opgaven med at generere en sådan liste fra bunden synes at være så svært som at være helt upraktisk. Faktisk er det samlede antal måder at vælge hundrede studerende fra de fire hundrede ansøgere større end antallet af atomer i det kendte univers!, Således kunne ingen fremtidig civilisation nogensinde håbe på at opbygge en supercomputer, der er i stand til at løse problemet med brute force; det vil sige ved at kontrollere enhver mulig kombination af 100 studerende. Imidlertid kan denne tilsyneladende vanskelighed kun afspejle manglen på opfindsomhed hos din programmør. Faktisk er et af de udestående problemer inden for Datalogi at afgøre, om der findes spørgsmål, Hvis svar hurtigt kan kontrolleres, men som kræver en umulig lang tid at løse ved enhver direkte procedure., Problemer som den ovenfor nævnte synes bestemt at være af denne art, men indtil videre har ingen formået at bevise, at nogen af dem virkelig er så hårde, som de ser ud, dvs.at der virkelig ikke er nogen mulig måde at generere et svar ved hjælp af en computer. Stephen Cook og Leonid Levin formuleret P (dvs, let at finde) versus NP (dvs, let at kontrollere) problem selvstændigt i 1971.
Billedkredit: til venstre, Stephen Cook af Ji.. Janekekek (beskåret). CC BY-SA 3.0