Jenseits von NP: Ein intuitiveres Komplexitätsproblem
Der Autor hinterfragt die Verwendung des Halteproblems als kanonisches Beispiel für ein Problem, das schwieriger ist als NP-vollständig, und argumentiert, dass es verwirrend und unintuitiv ist. Obwohl unentscheidbar, kann die Überprüfung einer "Ja"-Antwort auf das Halteproblem durch Ausführen des Programms für eine endliche Anzahl von Schritten erfolgen. Eine leichter verständliche Alternative wird vorgestellt: das Bewegen einer Spielfigur auf einem unendlichen Gitter, um einen Zielpunkt zu erreichen. Dieses Problem ist PSPACE-vollständig in niedrigeren Dimensionen, aber seine Komplexität explodiert mit zunehmender Dimension und erreicht schließlich ACKERMANN-Vollständigkeit, was visuell eine Komplexität weit über NP-Problemen hinaus demonstriert.