Să presupunem că organizați locuințe pentru un grup de patru sute de studenți. Spațiul este limitat și doar o sută dintre studenți vor primi locuri în cămin. Pentru a complica lucrurile, decanul v-a oferit o listă de perechi de studenți incompatibili și a solicitat ca nicio pereche din această listă să nu apară în alegerea finală., Acesta este un exemplu de ceea ce informaticienii numesc o problemă NP, deoarece este ușor să verificați dacă o alegere dată de o sută de studenți propusă de un coleg este satisfăcătoare (adică nicio pereche luată din lista colegului dvs. nu apare și pe lista de la biroul decanului), cu toate acestea sarcina de a genera o astfel de listă de la zero pare a fi atât de grea încât să fie complet nepractică. Într-adevăr, numărul total de moduri de a alege o sută de studenți din cei patru sute de solicitanți este mai mare decât numărul de atomi din universul cunoscut!, Astfel, nici o civilizație viitoare nu ar putea spera vreodată să construiască un supercomputer capabil să rezolve problema prin forță brută; adică verificând fiecare combinație posibilă de 100 de studenți. Cu toate acestea, această dificultate aparentă poate reflecta doar lipsa de ingeniozitate a programatorului tău. De fapt, una dintre problemele remarcabile în informatică este de a determina dacă există întrebări al căror răspuns poate fi verificat rapid, dar care necesită un timp imposibil de lung pentru a fi rezolvate prin orice procedură directă., Probleme precum cele enumerate mai sus par a fi de acest fel, dar până acum nimeni nu a reușit să demonstreze că oricare dintre ele este într-adevăr atât de greu pe cât apar, adică că nu există într-adevăr o modalitate fezabilă de a genera un răspuns cu ajutorul unui computer. Stephen Cook și Leonid Levin au formulat problema P (adică ușor de găsit) față de NP (adică ușor de verificat) în mod independent în 1971.credit Imagine: în stânga, Stephen Cook De Jiří Janíček (decupat). CC BY-SA 3.0