50 Jahre alte Vermutung über Raum vs. Zeit in der Informatik geknackt

Eine zentrale Frage in der Komplexitätstheorie ist die Beziehung zwischen P und PSPACE, Klassen, die Probleme umfassen, die in angemessener Zeit bzw. in angemessenem Raum gelöst werden können. Intuitiv ist der Raum eine leistungsfähigere Ressource als die Zeit, da er wiederverwendbar ist. 50 Jahre lang versuchten Forscher zu beweisen, dass PSPACE größer als P ist, was bedeutet, dass einige Probleme nicht schnell lösbar sind, aber mit begrenztem Raum lösbar sind. Hopcroft, Paul und Valiant machten 1975 eine Entdeckung und zeigten, dass der Raum etwas leistungsfähiger ist als die Zeit. Dieser Fortschritt war jedoch durch den 'Simulations'-Ansatz begrenzt. Ryan Williams durchbrach schließlich die Blockade mit einem neuartigen Ansatz und löste das langjährige Problem.