Die letzte Frage der Informatik
Ein 50 Jahre altes Problem der theoretischen Informatik – bekannt als P vs. NP – entzieht sich noch immer einer Lösung. Dabei könnte ein Beweis dieser obskuren mathematischen Vermutung die Informatik für immer verändern.
Montag, der 19. Juli 2021, war wieder einer dieser Tage. Ein Tag, mitten im zweiten Pandemie-Sommer, an dem anscheinend alles schiefgeht. Jedenfalls liest sich der Tweet eines führenden Informatikers so, der eigentlich auf dem Gebiet der Komplexitätstheorie forscht, sich nun aber heftig über den administrativen Schlamassel bei einer führenden Fachzeitschrift beklagt – und seinen Tweet mit einem sehr geladenen „Happy Monday“ beendet. Dabei hätte dieser Tag vielleicht tatsächlich ein glücklicher Montag sein können – in irgendeinem Paralleluniversum. Denn an diesem Tag erschien in der Online-Ausgabe der angesehenen Fachzeitschrift „ACM Transactions on Computational Theory“, die sich mit „herausragender Forschung zu den Grenzen machbarer Berechnungen“ befasst, ein Paper, in dem angeblich eine Lösung für das Problem aller Probleme stand – dem Heiligen Gral der theoretischen Informatik.
Dieses Problem – bekannt als „P versus NP“ – gilt als das wichtigste Problem der theoretischen Informatik. Für seine Lösung ist eine Prämie von einer Million Dollar ausgesetzt. Es befasst sich mit zentralen Fragen zu den Verheißungen, Grenzen und Ambitionen der Computertechnik: Welche Probleme können Computer realistischerweise lösen? Wie viel Zeit werden sie dafür benötigen? Und warum sind manche Probleme schwieriger als andere? Was heißt eigentlich „schwierig“?