Ruang batas bawah terbaik saat ini untuk SAT?

apa batas bawah ruang terbaik saat ini untuk SAT?

Dengan batas bawah ruang yang saya maksud di sini adalah jumlah sel worktape yang digunakan oleh mesin Turing yang menggunakan alfabet biner worktape. Istilah aditif konstan tidak dapat dihindari karena TM dapat menggunakan kondisi internal untuk mensimulasikan jumlah sel worktape yang tetap. Namun, saya tertarik untuk mengendalikan konstanta multiplikasi yang sering dibiarkan tersirat: setup biasa memungkinkan kompresi konstan sewenang-wenang melalui huruf yang lebih besar sehingga konstanta multiplikatif tidak relevan di sana, tetapi dengan alfabet tetap harus dimungkinkan untuk memperhitungkannya.

Sebagai contoh, SAT membutuhkan lebih dari ruang; jika tidak maka batas atas ruang ini akan mengarah ke batas atas waktu dengan simulasi, dan dengan demikian gabungan batas waktu ruang-waktu lebih rendah untuk SAT akan dilanggar (lihat pertanyaan terkait). Tampaknya juga mungkin untuk meningkatkan argumen ini untuk berargumen bahwa SAT memerlukan setidaknya ruang untuk beberapa positif kecil yang kira-kira seperti , di mana adalah eksponen konstan dalam simulasi ruang-dibatasi TM oleh TM yang dibatasi waktu. $\log\log n + c$ $n^{1+o(1)}$ $n^{1.801+o(1)}$ $\delta\log n + c$ $\delta$ $0.801/C$ $C$

Sayangnya biasanya cukup besar (dan tentunya setidaknya 2 dalam simulasi biasa, di mana kaset TM pertama kali dikodekan pada satu kaset melalui alfabet yang lebih besar). Batas-batas seperti dengan agak lemah, dan saya akan sangat tertarik pada ruang batas bawah dari . Batas bawah waktu tak terbatas dari langkah , untuk beberapa konstanta yang cukup besar , akan menyiratkan ruang seperti batas bawah melalui simulasi. Namun, batas bawah waktu untuk saat ini tidak diketahui, apalagi untuk besar . $C$ $\delta \ll 1$ $\log n + c$ $\Omega(n^d)$ $d > 1$ $\Omega(n^d)$ $d>1$ $d$

Dengan kata lain, saya sedang mencari sesuatu yang akan menjadi konsekuensi dari batas bawah waktu superlinear untuk SAT, tetapi yang mungkin dapat diperoleh lebih langsung.

cc.complexity-theory sat lower-bounds space-bounded space-complexity András Salamon
sumber

seperti pada jawaban yang lain (misalnya oleh RW), fokus pada batas waktu atau ruang batas bawah secara terpisah tampaknya tidak terjangkau dan hanya memiliki batas yang diketahui umum / lemah, dan penelitian terkemuka di bidang tersebut tampaknya memunculkan konsep yang relatif lebih baru kompleksitas ruang-waktu gabungan.

vzn

Jawaban:

Sepertinya yang terikat paling dikenal (untuk mesin Turing multitape) adalah logaritmik.

Misalkan bit dari worktape biner sudah cukup untuk memutuskan apakah ada rumus CNF bit yang memuaskan, untuk semua yang cukup besar . Dengan simulasi standar, TM dengan menyatakan bahwa penggunaan paling bit ruang dapat disimulasikan oleh TM yang memiliki paling konfigurasi yang berbeda . Setiap kali mesin menerima, ada urutan (nondeterministic) bergerak mencapai keadaan penerimaan yang paling banyak selama jumlah konfigurasi ini. Ketika , ini paling banyak (perhatikan bahwa tetap sama untuk semua panjang input $\delta\log n$ $n$ $n$ $q$ $s$ $qns2^s = 2^{s+\log n + \log s + \log q}$ $s = \Omega(\log n)$ $2^{s(2+o(1))}$ $q$ $n$ ). Pada kaset penghitung yang terpisah, pertama-tama dapat menulis kuantitas ini di unary, kemudian pada setiap langkah simulasi hapus salah satu simbol penghitung, dan hentikan perhitungan jika pernah kehabisan simbol penghitung. Ini menciptakan faktor konstan overhead (sekitar 3), yang diserap oleh istilah dalam eksponen. Maka langkah sudah cukup. $M$ $o(1)$ $2^{s(2+o(1))}$

Dengan asumsi , maka produk ruang-waktu paling banyak . $s \le \delta\log n$ $\delta\log n2^{\delta\log n(2+o(1))} = n^{\delta(2+o(1))}$

Rahul Santhanam menunjukkan pada tahun 2001 (lihat doi: 10.1016 / S0020-0190 (00) 00227-1 ) bahwa produk ruang-waktu untuk mesin Turing yang menentukan SAT harus setidaknya ; argumennya juga berlaku untuk mesin nondeterministic. Oleh karena itu , dan setidaknya bit dari worktape biner diperlukan. $\Omega(n^{2-o(1)})$ $\delta \ge 1$ $\log n$

Lebih umum, worktape tambahan dan alfabet worktape yang lebih besar mengubah eksponen dengan faktor konstan. Ini pada akhirnya mengurangi faktor , tetapi batas bawah ruang masih . $\delta$ $\Omega(\log n)$

András Salamon
sumber

Mungkin kita dapat membuktikan ruang batas bawah untuk SAT dengan cara ini (tapi saya tidak yakin dengan analisis batas / asimptotik, sehingga jawaban saya bisa salah total). $\log n$

Pada model mesin Turing dengan satu tape input read-only dan satu tape work, keduanya di atas alfabet biner , untuk setiap penentu dengan status pada input ukuran kita memiliki itu: $\Sigma = \{0,1\}$ $c$ $n$

T (n) \leq c 2^{S (n)} n S (n) (1)

$T(n) \leq c \, 2^{S(n)} \, n \, S(n) \quad (1)$

jika tidak, mesin Turing akan berulang selamanya (komponen mewakili semua konfigurasi pita yang mungkin, komponen mewakili posisi kepala kaset input, sedangkan komponen mewakili posisi kepala pita kerja). Pada satu pita, satu kepala TM lebih dari alfabet biner (1) menjadi . $2^{S(n)}$ $n$ $S(n)$ $T(n) \leq c 2^{S(n)} S(n)$

Mengalikan kedua istilah dengan dan menerapkan tradeoff waktu-ruang umum untuk SAT, kita dapatkan: $S(n)$

n^{1.801 + o (1)} \leq S (n) \cdot T (n) \leq c S (n)^{2} 2^{S (n)} n

$n^{1.801+o(1)} \leq S(n)\cdot T(n) \leq c \, S(n)^2 \, 2^{S(n)} \, n$

Jadi memilih spasi batas atas seperti untuk SAT akan menyebabkan kontradiksi, memang $S(n) \leq (\log n)^{1 - \epsilon}$

lim_{n \to \infty} \frac{n^{1.801}}{c ((\log n)^{1 - ϵ})^{2} 2^{(\log n)^{1 - ϵ}} n} =

$\lim_{n \to \infty} \frac{n^{1.801}}{ c \, ((\log n)^{1-\epsilon})^2 2^{(\log n)^{1-\epsilon}} n } =$

lim_{n \to \infty} (0.801 \cdot \log n - \log c - 2 (1 - ϵ) \log (\log n) - (\log n)^{1 - ϵ}) = \infty

$\lim_{n \to \infty} \Big( 0.801 \cdot \log n - \log c - 2 (1- \epsilon) \log (\log n) - (\log n)^{1-\epsilon}\Big) = \infty$

Marzio De Biasi
sumber

Tampaknya setidaknya ada dua cara umum untuk menunjukkan bahwa batas atas mengarah ke kontradiksi. Terutama dalam pikiran saya menggunakan (dasarnya identik, tapi sedikit lebih mudah untuk bekerja dengan) ketidaksetaraan untuk beberapa konstan . Langkah terakhir yang Anda berikan juga bisa dibuat lebih kuat, sebagai kontradiksi berikut bahkan dari untuk .

o (\log n)

$o(\log n)$

T (n) \leq 2^{\log n + C . S (n)}

$T(n) \le 2^{\log n + C.S(n)}$

C

$C$

S (n) \leq δ \log n

$S(n) \le \delta\log n$

δ < 0.801 / C

$\delta < 0.801/C$

András Salamon

@ AndrásSalamon: di sisi terikat , Anda tidak dapat mengharapkan peningkatan mudah: dari S. Buss dan R. Williams. Batas pada Perdagangan-Alternatif Bukti untuk Batas Waktu-Ruang Bawah, 2012: "Kami menunjukkan bahwa teknik-teknik baru terbukti diperlukan untuk membuktikan batas waktu-ruang yang lebih baik untuk masalah kepuasan. Yaitu, metode" perdagangan-alternatif bukti "digunakan untuk menetapkan bahwa SAT tidak dapat diselesaikan dalam waktu dan spasi tidak dapat membuktikan sebuah batas waktu lebih rendah, untuk setiap ". Apakah kamu punya ide :-)?

S \cdot T

$S\cdot T$

n^{2 \cos (π / 7)}

$n^{2\cos(\pi /7)}$

n^{o (1)}

$n^{o(1)}$

n^{2 \cos (π / 7)} + ϵ

$n^{2\cos(\pi /7)}+\epsilon$

ϵ > 0

$\epsilon >0$

Marzio De Biasi

Saya pikir ini adalah tentang sejauh mana seseorang dapat menggunakan batas ruang-waktu, tepatnya karena pendekatan Ryan sejauh batas ini pergi.

András Salamon

Untuk bahkan menyimpan instance SAT Anda perlu dan membacanya Anda perlu waktu. Bukankah ini membuktikan ST batas bawah?

Ω (n)

$\Omega(n)$

Ω (n)

$\Omega(n)$

Ω (n^{2})

$\Omega(n^2)$

T ....

@ Turbo, tidak jelas bahwa setiap algoritma untuk memutuskan SAT harus menyimpan contoh: membuktikan bit ruang deterministik batas bawah akan menunjukkan .

Ω (n)

$\Omega(n)$

L ⊊ N P

$\mathsf{L} \subsetneq \mathsf{NP}$

András Salamon