Antag att du organiserar boende för en grupp av fyrahundra universitetsstudenter. Utrymmet är begränsat och endast ett hundra av studenterna kommer att få platser i sovsalen. För att komplicera saker har Dekanen gett dig en lista över par av inkompatibla studenter och begärt att inget par från den här listan visas i ditt slutliga val., Det här är ett exempel på vad Dataforskare kallar ett NP-problem, eftersom det är lätt att kontrollera om ett visst val av hundra studenter som föreslås av en medarbetare är tillfredsställande (dvs inget par som tas från din medarbetare”s-lista visas också på listan från dekanens kontor), men uppgiften att generera en sådan lista från början verkar vara så svår att vara helt opraktisk. Faktum är att det totala antalet sätt att välja hundra studenter från de fyra hundra sökandena är större än antalet atomer i det kända universum!, Således kunde ingen framtida civilisation någonsin hoppas på att bygga en superdator som kunde lösa problemet med brute force; det vill säga genom att kontrollera varje möjlig kombination av 100 studenter. Denna uppenbara svårighet kan dock bara återspegla bristen på uppfinningsrikedom hos din programmerare. Faktum är att ett av de utestående problemen inom datavetenskap bestämmer om det finns frågor vars svar snabbt kan kontrolleras, men som kräver en omöjligt lång tid att lösa genom något direkt förfarande., Problem som den som anges ovan verkar verkligen vara av detta slag, men hittills har ingen lyckats bevisa att någon av dem verkligen är så svåra som de verkar, dvs att det verkligen inte finns något genomförbart sätt att generera ett svar med hjälp av en dator. Stephen Cook och Leonid Levin formulerade P (dvs lätt att hitta) mot NP (dvs lätt att kontrollera) problem självständigt 1971.
bild kredit: till vänster, Stephen Cook av Jiří Janíček (beskurna). CC BY-SA 3.0