Ist der Memory-Runtime-Kompromiss ein Äquivalent zu Heisenbergs Unsicherheitsprinzip?

Question

Wenn ich an einem Algorithmus arbeite, um ein Computerproblem zu lösen, erlebe ich oft, dass die Geschwindigkeit durch mehr Speicher verwendet werden kann, und der Speicherverbrauch kann zum Preis einer höheren Laufzeit verringert werden, aber ich kann das Produkt der Laufzeit und des Produkts niemals erzwingen Verbrauchter Speicher unterhalb einer eindeutig tastbaren Grenze. Dies ähnelt formell dem Unsicherheitsprinzip von Heisenberg: Das Produkt der Positionsunsicherheit und die Unsicherheit des Impulses eines Partikels kann nicht weniger als eine bestimmte Schwelle sein.

Gibt es einen Theorem der Informatik, der dasselbe behauptet? Ich denke, es sollte möglich sein, etwas Ähnliches aus der Theorie der Turing -Maschinen abzuleiten.

(Ich habe diese Frage ursprünglich gestellt Paketüberfluss.)

Answer 1

Dieses Phänomen ist in der Informatik als a bekannt Zeitraum-Kompromiss. Zum Beispiel Ryan Williams bewiesen Wenn ein Computer in Instanzen von Größe $ n $ in zeit $ t $ löst und Speicher $ s $ dann verwendet, dann $ t cdot s geq n^{1.8} $. (Wir erwarten nicht, dass dies eng ist.) A klassisches Ergebnis stellt fest, dass bei der Erkennung von Palindromen auf a Turing Maschine, $ T cdot s = omega (n^2) $.