Tradeoff ruang-waktu batas bawah

Setelah diskusi tentang batas bawah untuk 3SAT [ 1 ], saya bertanya-tanya apa hasil batas bawah utama yang dirumuskan sebagai pertukaran ruang-waktu. Saya mengecualikan hasil seperti, katakanlah, teorema Savitch; entri yang bagus akan fokus pada satu masalah dan batasannya. Contohnya adalah:

"Biarkan T dan S menjadi batas waktu berjalan dan ruang dari setiap algoritma SAT. Maka kita harus memiliki T⋅S≥n2cos (π / 7) −o (1) sangat sering." (Diberikan dalam [ 1 ] oleh Ryan Williams.)

atau

"SAT tidak dapat diselesaikan secara bersamaan dalam waktu n ^{1 + 0 (1)} dan ruang n ^1-ε untuk ε> 0 pada mesin Turing nondeterministik akses-acak umum." (Lance Fortnow dalam 10.1109 / CCC.1997.612300)

Lebih jauh, saya memasukkan definisi kelas kompleksitas tradeoff ruang-waktu alami (tidak termasuk kelas sirkuit).

Berikut beberapa referensi tambahan. Lebih banyak dapat ditemukan dengan melihat kertas yang mengutip ini.

$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)$ . Pekerjaan selanjutnya oleh Beame, Saks, Sun, dan Vee (2000) membuktikan pertukaran ruang-waktu untuk perhitungan acak.

$TS \geq \Omega(n^2)$