P vs. PSPACE: Ist der Raum rechnerisch mächtiger als die Zeit?

Eine zentrale Frage in der Komplexitätstheorie ist die Beziehung zwischen den Komplexitätsklassen P und PSPACE. P umfasst Probleme, die in angemessener Zeit lösbar sind, während PSPACE sich mit der Raumkomplexität befasst. Die vorherrschende Annahme ist, dass PSPACE größer als P ist, da der Raum im Gegensatz zur Zeit wiederverwendbar ist. Um dies zu beweisen, müsste man Probleme in PSPACE zeigen, die nicht in polynomieller Zeit lösbar sind. Der Artikel beschreibt den Durchbruch von Hopcroft, Paul und Valiant aus dem Jahr 1975, der den leichten Vorteil des Raums gegenüber der Zeit aufzeigte, aber der Fortschritt stagnierte. Die Arbeit von Ryan Williams hat schließlich den Stillstand durchbrochen und neue Perspektiven zur Lösung des Problems P vs. PSPACE eröffnet.