stel dat u huisvesting organiseert voor een groep van vierhonderd universiteitsstudenten. De ruimte is beperkt en slechts honderd studenten krijgen plaats in de slaapzaal. Om de zaken te compliceren, de decaan heeft u voorzien van een lijst van paren van onverenigbare studenten, en verzocht dat geen paar uit deze lijst verschijnen in uw uiteindelijke keuze., Dit is een voorbeeld van wat computerwetenschappers een NP-probleem noemen, omdat het gemakkelijk is om te controleren of een bepaalde keuze van honderd studenten die door een collega worden voorgesteld bevredigend is (dat wil zeggen, geen paar uit de lijst van uw collega ‘ s staat ook op de lijst van het kantoor van de decaan), maar de taak van het genereren van een dergelijke lijst vanuit het niets lijkt zo moeilijk te zijn dat volledig onpraktisch. Inderdaad, het totale aantal manieren om honderd studenten uit de vierhonderd kandidaten te kiezen is groter dan het aantal atomen in het bekende universum!, Zo zou geen enkele toekomstige beschaving ooit kunnen hopen een supercomputer te bouwen die in staat is het probleem met brute kracht op te lossen; dat wil zeggen, door elke mogelijke combinatie van 100 studenten te controleren. Deze schijnbare moeilijkheid kan echter alleen het gebrek aan vindingrijkheid van uw programmeur weerspiegelen. In feite is een van de openstaande problemen in de informatica het bepalen of er vragen bestaan waarvan het antwoord snel kan worden gecontroleerd, maar die onmogelijk veel tijd vergen om via een directe procedure op te lossen., Problemen zoals de hierboven genoemde lijken zeker van dit soort te zijn, maar tot nu toe is niemand erin geslaagd om te bewijzen dat een van hen echt zo moeilijk zijn als ze lijken, dat wil zeggen, dat er echt geen haalbare manier is om een antwoord te genereren met behulp van een computer. Stephen Cook en Leonid Levin formuleerden in 1971 onafhankelijk van elkaar het probleem P (easy to find) versus NP (easy to check).
beeld door: links Stephen Cook van Jiří Janíček (bijgesneden). CC BY-SA 3.0