Předpokládejme, že organizujete ubytování pro skupinu čtyř set vysokoškolských studentů. Prostor je omezený a pouze sto studentů obdrží místa v koleji. To komplikuje věci, Děkan poskytl seznam párů neslučitelné studenty, a požadoval, aby žádná dvojice z tohoto seznamu objeví v konečném výběru., To je příklad toho, co počítač vědci nazývají NP-problém, protože to je snadné zkontrolovat, zda daný výběr sto studentů navržené spolupracovník je uspokojivý (tj., ne pár přijata od spolupracovníka“s seznamu se objeví také na seznamu Děkana“s office), nicméně úkol generovat takový seznam od nuly se zdá být tak těžké, jak být zcela nepraktické. Celkový počet způsobů výběru sto studentů ze čtyř set žadatelů je ve skutečnosti větší než počet atomů ve známém vesmíru!, Tedy žádná budoucí civilizace by mohla někdy doufat, že vytvořit superpočítač schopný řešit problém hrubou silou; to je tím, že kontroluje všechny možné kombinace 100 studentů. Tato zjevná obtíž však může odrážet pouze nedostatek vynalézavosti vašeho programátora. Ve skutečnosti je jedním z nevyřešených problémů v informatice určení, zda existují otázky, jejichž odpověď lze rychle zkontrolovat, ale které vyžadují nemožně dlouhou dobu k vyřešení jakýmkoli přímým postupem., Problémy, jako je ten, který je uveden výše, se jistě zdají být tohoto druhu, ale zatím se nikomu nepodařilo prokázat, že některý z nich je opravdu tak tvrdý, jak se zdá, tj. Stephen Cook a Leonid Levin formulovali problém P (tj.
obrázek kredit: vlevo Stephen Cook od Jiřího Janíčka (oříznutý). CC BY-SA 3.0