Apa batas bawah terbaik saat ini pada 3SAT?

Apa batas bawah terbaik saat ini untuk waktu dan kedalaman rangkaian untuk 3SAT?

Sejauh yang saya tahu, batas bawah waktu "model-independen" paling terkenal untuk SAT adalah sebagai berikut. Biarkan dan S menjadi batas waktu dan ruang berlari dari algoritma SAT apa pun. Maka kita harus memiliki T ⋅ S ≥ n 2 cos ( π / 7 ) - o ( 1 ) tanpa batas. Catatan 2 cos ( π / 7 ) ≈ 1.801 . (Hasil yang dikutip Suresh sedikit usang.) Hasil ini muncul di STACS 2010, tapi itu adalah abstrak yang diperluas dari makalah yang jauh lebih lama, yang bisa Anda dapatkan di sini:$T$$S$$T \cdot S \geq n^{2 \cos(\pi/7) - o(1)}$$2 \cos(\pi/7) \approx 1.801$http://www.cs.cmu.edu/~ryanw/automated-lbs.pdf

Tentu saja, pekerjaan di atas dibangun di atas banyak pekerjaan sebelumnya yang disebutkan dalam blog Lipton (lihat jawaban Suresh). Juga, ketika batas ruang S mendekati n, waktu batas bawah T juga mendekati n. Anda dapat membuktikan "pertukaran ruang-waktu" yang lebih baik di rezim ini; lihat survei Dieter van Melkebeek tentang batas bawah ruang-waktu SAT dari 2008.

Jika Anda membatasi diri pada mesin Turing multitape, Anda dapat membuktikan tanpa batas sering. Itu dibuktikan oleh Rahul Santhanam, dan mengikuti dari batas bawah serupa yang dikenal untuk PALINDROMES dalam model ini. Kami percaya Anda harus dapat membuktikan batas bawah kuadratik yang "model-independen" tapi itu sulit dipahami untuk beberapa waktu.$T \cdot S \geq n^{2-o(1)}$

Untuk sirkuit yang tidak seragam dengan fan-in yang terikat, saya tahu tidak ada kedalaman yang lebih baik daripada .$\log n$

$o(n)$$n^c$$c$$\sqrt{3}$

$\Omega(n^c)$$c > 1$

Pemahaman saya sama dengan Lev Reyzin. Ada kemungkinan bahwa ada algoritma lengkap deterministik untuk SAT yang berjalan di ruang O (n) dan dalam waktu O (n). Sungguh menakjubkan bahwa keberadaan algoritma yang sedemikian efisien tidak dilarang.