Wissenschaftler lieben es, Dinge zu kategorisieren – zumindest auf abstrakter Ebene. Chemiker teilen beispielsweise alle Elemente in das Periodensystem ein, Biologen ordnen Lebewesen nach Familien und Arten, und Mathematiker haben im vergangenen Jahrzehnt, nach langer Suche, alle endlichen einfachen Gruppen gefunden und aufgelistet.

Informatiker suchen ebenfalls nach Ordnung, wenn auch ein wenig anders: Sie sortieren Probleme nach ihrer Komplexität. Bereits in der Vergangenheit haben sie herausgefunden, dass gewisse Aufgaben für Computer sehr einfach zu lösen sind. Bei ihnen wächst mit der Länge des Problems die zur Lösung nötige Rechenzeit bloß langsam (polynomial) an. Aus Sicht von Informatikern gehören sie damit zur so genannten Komplexitätsklasse P.

Probleme, die schwer zu lösen sind, sich aber einfach überprüfen lassen, zählen hingegen zur Klasse NP. Ein Beispiel ist ein anspruchsvolles Sudoku-Rätsel: Bei diesem ist es schwierig, die passenden Zahlen zu finden. Hat man sie jedoch einmal ausgetüftelt oder bekommt ein ausgefülltes Blatt präsentiert, lässt sich leicht überprüfen, ob es korrekt ist. Ob P und NP wirklich verschiedene Klassen sind oder ob man einfach noch keinen Algorithmus kennt, der die entsprechenden Probleme effizient löst, zählt zu den wichtigsten offenen Fragen der theoretischen Informatik. Sie ist eines der sieben Millennium-Probleme, deren Lösung das Clay Mathematics Institute mit je einer Million US-Dollar belohnt.

Mit P und NP fängt der Spaß aber erst an. Computerwissenschaftler haben mittlerweile eine Hierarchie von Komplexitätsklassen herausgearbeitet, von sehr einfachen hin zu extrem anspruchsvollen Aufgaben …