Kompromis czasoprzestrzenny w dolnych granicach

Po dyskusji na temat dolnych granic dla 3SAT [ 1 ] zastanawiam się, jakie są główne wyniki dolnej granicy sformułowane jako kompromisy czasoprzestrzenne. Wykluczam wyniki takie jak, powiedzmy, twierdzenie Savitcha; dobry wpis koncentrowałby się na jednym problemie i jego granicach. Przykładem może być:

„Niech T i S będą czasem działania i przestrzenią dowolnego algorytmu SAT. Zatem musimy mieć T⋅S≥n2cos (π / 7) −o (1) nieskończenie często.” (Podane w [ 1 ] przez Ryana Williamsa.)

lub

„SAT nie może być rozwiązany jednocześnie w czasie n ^{1 + 0 (1)} i przestrzeni n ^1-ε dla dowolnego ε> 0 na ogólnych niedeterministycznych maszynach Turinga o swobodnym dostępie.” (Lance Fortnow w 10.1109 / CCC.1997.612300)

Ponadto dołączam definicje klas złożoności kompromisu przestrzenno-czasowego (z wyłączeniem klas obwodów).

Oto kilka dodatkowych referencji. Więcej można znaleźć, przeglądając dokumenty, które je cytują.

$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)$