Angenommen, Sie organisieren Unterkünfte für eine Gruppe von vierhundert Studenten. Der Platz ist begrenzt und nur einhundert der Schüler erhalten Plätze im Schlafsaal. Um die Sache zu erschweren, hat der Dekan Ihnen eine Liste von Paaren inkompatibler Schüler zur Verfügung gestellt und darum gebeten, dass kein Paar aus dieser Liste in Ihrer endgültigen Wahl erscheint., Dies ist ein Beispiel dafür, was Informatiker ein NP-Problem nennen, da es leicht zu überprüfen ist, ob eine bestimmte Auswahl von hundert Studenten, die von einem Mitarbeiter vorgeschlagen wird, zufriedenstellend ist (dh kein Paar aus der Liste Ihres Kollegen erscheint auch auf der Liste aus dem Dekanat), aber die Aufgabe, eine solche Liste von Grund auf neu zu erstellen, scheint so schwer zu sein, dass sie völlig unpraktisch ist. In der Tat ist die Gesamtzahl der Möglichkeiten, hundert Studenten aus den vierhundert Bewerbern auszuwählen, größer als die Anzahl der Atome im bekannten Universum!, So konnte keine zukünftige Zivilisation jemals hoffen, einen Supercomputer zu bauen, der das Problem mit roher Gewalt lösen kann.das heißt, indem jede mögliche Kombination von 100 Studenten überprüft wird. Diese offensichtliche Schwierigkeit kann jedoch nur den Mangel an Einfallsreichtum Ihres Programmierers widerspiegeln. Tatsächlich besteht eines der herausragenden Probleme in der Informatik darin, festzustellen, ob Fragen existieren, deren Antwort schnell überprüft werden kann, die jedoch eine unglaublich lange Zeit erfordern, um sie durch ein direktes Verfahren zu lösen., Probleme wie die oben aufgeführten scheinen sicherlich von dieser Art zu sein, aber bisher hat es niemand geschafft zu beweisen, dass eine von ihnen wirklich so schwer ist, wie sie erscheinen, dh dass es wirklich keine Möglichkeit gibt, eine Antwort mit Hilfe eines Computers zu generieren. Stephen Cook und Leonid Levin formulierten 1971 unabhängig voneinander das Problem P (d. H. Leicht zu finden) gegenüber NP (d. H. Leicht zu überprüfen).
Bildnachweis: auf der linken Seite Stephen Cook von Jiří Janíček (beschnitten). CC-BY-SA-3.0