Raum-Zeit-Kompromiss Untergrenzen

Nach der Diskussion über untere Schranken für 3SAT [ 1 ] frage ich mich, was die wichtigsten Ergebnisse für untere Schranken sind, die als Raum-Zeit-Kompromisse formuliert wurden. Ich schließe Ergebnisse aus, wie zum Beispiel den Satz von Savitch; Ein guter Beitrag würde sich auf ein einzelnes Problem und seine Grenzen konzentrieren. Ein Beispiel wäre:

"Sei T und S die Laufzeit und der Raum eines jeden SAT-Algorithmus. Dann müssen wir unendlich oft T⋅S≥n2cos (π / 7) −o (1) haben." (Gegeben in [ 1 ] von Ryan Williams.)

oder

"SAT kann nicht gleichzeitig in n ^{1 + 0 (1)} Zeit und n ^{1 - ε} Raum für ε> 0 auf allgemeinen nicht deterministischen Turing-Maschinen mit wahlfreiem Zugriff gelöst werden." (Lance Fortnow in 10.1109 / CCC.1997.612300)

Außerdem füge ich Definitionen von Komplexitätsklassen für natürliche Raum-Zeit-Kompromisse (ohne Schaltungsklassen) hinzu.

Hier einige zusätzliche Referenzen. Weitere Informationen finden Sie in den Papieren, in denen diese zitiert werden.

$P$$T^2 S \geq \Omega(n^3)$

$O(n)$$O(1)$$k+1$$T S \geq \Omega(n^2)$$k$

$S \leq o(n)$$T \geq \omega(n)$

$TS \geq \Omega(n^2)$ gilt für Multitape-Turingmaschinen, die SAT lösen und auf Cobhams analoger Untergrenze für PALINDROMES aufbauen.