Bahnbrechende Entdeckung: Deutlich weniger Speicherplatz für Berechnungen benötigt

Ryan Williams, Informatiker am MIT, hat eine bahnbrechende Entdeckung gemacht, die 50 Jahre an Annahmen über den Kompromiss zwischen Rechenplatz und -zeit widerlegt. Die traditionelle Theorie besagte, dass eine t-stufige Berechnung ungefähr t Bits Speicher benötigt. Williams bewies jedoch, dass jedes in der Zeit t lösbare Problem nur etwa √t Bits Speicher benötigt. Dieses Ergebnis basiert auf der Reduktion des Problems auf ein äquivalentes Problem, das den Speicherplatz geschickt wiederverwendet und so Informationen komprimiert. Die Forschung legt nahe, dass der Engpass bei der Berechnung nicht die Speicherkapazität ist, sondern die effiziente Nutzung des Speichers.