tegyük fel, hogy négyszáz egyetemi hallgató csoportja számára lakhatási szállást szervez. A hely korlátozott, a diákok közül csak száz kap helyet a kollégiumban. A dolgok bonyolítása érdekében a dékán megadta az összeférhetetlen diákok párjainak listáját, és kérte, hogy ebből a listából egyetlen pár se jelenjen meg a végső választásban., Ez egy példa, amit a számítógép tudósok hívás egy NP-probléma, mivel ez könnyen ellenőrizhető, ha egy adott választás száz diákok által javasolt egy munkatárs kielégítő (azaz, nem párt kell venni a munkatárs”s listája is megjelenik a listán a Dékán”s office), azonban a feladatot generál egy ilyen lista a semmiből tűnik, hogy olyan nehéz, mint hogy teljesen kivitelezhetetlen. Valójában a négyszáz pályázóból száz hallgató kiválasztásának teljes száma nagyobb, mint az ismert univerzum atomjainak száma!, Így egyetlen jövőbeli civilizáció sem remélheti, hogy szuperszámítógépet épít, amely képes a probléma megoldására brutális erővel; vagyis 100 diák minden lehetséges kombinációjának ellenőrzésével. Ez a látszólagos nehézség azonban csak a programozó találékonyságának hiányát tükrözi. Valójában a számítástechnika egyik kiemelkedő problémája annak meghatározása, hogy léteznek-e olyan kérdések, amelyek válaszát gyorsan ellenőrizni lehet, de amelyek lehetetlen hosszú időt igényelnek bármilyen közvetlen eljárással történő megoldáshoz., Az olyan problémák, mint a fent felsoroltak, minden bizonnyal ilyennek tűnnek, de eddig senki sem tudta bizonyítani, hogy bármelyikük valóban olyan nehéz, mint amilyennek látszik, azaz hogy valójában nincs megvalósítható módja annak, hogy egy számítógép segítségével választ generáljon. Stephen szakács és Leonid Levin 1971-ben önállóan fogalmazták meg a P (azaz könnyen megtalálható) és az NP (azaz könnyen ellenőrizhető) problémát.
Image credit: A bal oldalon, Stephen szakács Jiří Janíček (vágott). CC BY-SA 3.0