Apakah sirkuit berukuran kuasi polinomial untuk 3-SAT sepele?

Misalkan kita mempertimbangkan 3-SAT dengan variabel dan klausa . Saya sedang meneliti metode yang tampaknya mengambil waktu / ruang untuk memecahkan masalah SAT yang sesuai dengan deskripsi ini, untuk dalam kesalahan yang dapat disesuaikan dengan jumlah sewenang-wenang. Namun, ada yang menangkap. $v$ $c$ $O(v^{2+\log c})$

Metode ini membutuhkan seperangkat nilai yang dikomputasi, setelah itu dapat memecahkan masalah 3-SAT sewenang-wenang sesuai dengan deskripsi di atas. Nilai yang dikomputasi adalah seperangkat ukuran dengan masing-masing nilai mengambil ruang. Masalah sebenarnya adalah bahwa masing-masing nilai ini dapat mengambil waktu untuk menghitung. Ada kemungkinan saya dapat menemukan cara untuk mempercepat perhitungan ini. $O(v^{2+\log c})$ $O(1)$ $O(2^v)$

Saya berpikir bahwa batas itu sendiri mengalahkan batas atas yang disajikan dalam pertanyaan ini (untuk kecil ). Jadi saya bertanya-tanya, apakah ada cara sepele untuk mencapai batas atas yang saya jelaskan jika kita mengizinkan precomputasi? $c$ $O(v^{2+\log c})$

Saya ingin melanjutkan penelitian ini dan mudah-mudahan menerbitkan hasil saya jika semuanya berhasil, tetapi pertama-tama saya ingin tahu apakah ada cara sepele untuk melakukannya juga atau lebih baik.

MEMPERBARUI

Saya telah mempelajari masalah terkait selain meneliti algoritma ini. Saya mengajukan pertanyaan ini di situs IT Security StackExchange yang berkaitan dengan peretas kata sandi dan SAT, jika Anda tertarik. Setidaknya salah satu jawaban mencerminkan hal ini.

ds.algorithms sat upper-bounds Matt Groff
sumber

Anda bilang butuh O (N ^ 2 + logc) waktu / ruang ... Jadi tidak di PSPACE? Tetapi di QSPACE (Quasi-Space)?

Tayfun Bayar

@ Payayfun Bayar: Ini berjalan dalam

. Ini adalah algoritma deterministik yang memberikan hasil modulo

utama (perhatikan bahwa hasil ini cukup untuk sisa algoritma untuk menentukan tugas yang memuaskan). Itu bisa dijalankan untuk prime apa saja. Berjalan untuk lebih dari satu perdana meningkatkan peluangnya untuk menemukan tugas yang memuaskan. Ini memiliki peluang untuk menemukan tugas yang memuaskan, jika ada, dari

O (v^{(2 + \log c)})

$O(v^{(2+\log c)})$

p

$p$

(p - 1) / p

$(p-1)/p$

Matt Groff

Apakah perlu SPACE O (N ^ (2 + log (c)))?

Tayfun Bayar

@ Payayfun Bayar: Ya. Saya belum menemukan cara untuk mengurangi pertimbangan ruang.

Matt Groff

Saya akan mengusulkan untuk mengubah judul menjadi lebih tepat. Judul saat ini tidak terlihat menarik, sementara pertanyaannya sendiri terlihat sangat menarik.

Yoshio Okamoto

Jawaban:

Jika apa yang Anda pelajari berhasil, itu pasti tidak akan sepele.

Ini akan menyiratkan bahwa 3SAT memiliki sirkuit (tidak seragam) dengan ukuran . Kemudian, setiap bahasa di (dan hirarki waktu polinomial) akan memiliki quasi-polinomial (yaitu, sirkuit) ukuran. $n^{O(\log n)}$ $NP$ $n^{O(\log^c n)}$

Bahkan jika perlu waktu preprocessing untuk menghasilkan struktur data ukuran hanya yang kemudian dapat dengan benar menjawab pertanyaan acak 3SAT ukuran dalam waktu acak dengan probabilitas tinggi, 3SAT akan memiliki sirkuit ukuran kuasi-polinomial, menggunakan terjemahan yang dikenal dari algoritma acak ke sirkuit. Ini tidak akan meningkatkan batas waktu algoritma yang diketahui karena preprocessing, tetapi masih akan sangat menarik sebagai hasil yang tidak seragam. $2^{2^n}$ $2^{O(\log^2 n)}$ $n$ $2^{O(\log^2 n)}$

Apa yang Anda maksud dengan "dalam kesalahan yang dapat disesuaikan dengan jumlah yang sewenang-wenang"? Apakah algoritma ini diacak?

Ryan Williams
sumber

:Terima kasih atas jawaban anda. Algoritma tidak acak. Waktu aktual dari algoritma itu sendiri tidak sesederhana seperti yang saya jelaskan. Pada dasarnya, kita bisa menjalankannya melalui proses berulang untuk menghilangkan kesalahan. Jadi jika kita menjalankannya melalui

kali, probabilitas kesalahan akan berkurang di bawah

. Saya ragu-ragu untuk memberikan detailnya karena saya khawatir itu akan mengungkapkan terlalu banyak tentang algoritma.

x

$x$

1 / (2^{x})

$1/(2^x)$

Matt Groff

Bagaimana algoritme tidak dapat diacak, namun Anda dapat menjalankannya berulang kali untuk mengurangi kesalahan? Saya pikir Anda mungkin harus memberikan setidaknya beberapa detail lagi, untuk memahami pertanyaan Anda.

Ryan Williams

Algoritme-nya sedemikian rupa sehingga (jika berhasil), untuk setiap prime

, jika jumlah penugasan memuaskan bukan kelipatan

maka algoritme menemukan penugasan yang memuaskan.

p

$p$

p

$p$

$\;$ Dia (secara keliru) menyebutnya sebagai "perubahan menemukan tugas yang memuaskan, jika ada, dari

(p - 1) / p

$(p-1)/p$

$\hspace{0.9 in}$ Jika ketergantungan runtime pada

tidak besar, maka ini menghasilkan (deterministik) sirkuit berukuran kuasi-polinomial untuk SAT.

p

$p$

$\;\;$

Langkah preprocessing membutuhkan

. Dapatkah saya memiliki referensi ke "terjemahan yang diketahui dari algoritma acak ke sirkuit"? Jadi jika Anda ingin mengurangi kesalahan, Anda harus menjalankan preprocessing

kali. Saya ragu ini bisa diterjemahkan ke sirkuit semu. Keuntungan apa yang akan didapat dari algoritma yang sepele ini?

p

$p$

n

$n$

Zirui Wang

B P P \subset P / p o l y

$BPP \subset P/poly$

3 / 4

$3/4$

100 n

$100n$

2^{O (\log^{2} n)}

$2^{O(\log^2 n)}$

1 / 2^{n}

$1/2^n$

Ryan Williams

Saya tidak tahu apakah hasil Anda - jika valid - akan menjadi kemajuan non-sepele, tetapi di sini ada satu jenis masalah yang dapat Anda uji:

Masalah. Perbaiki fungsi . Mengingat , temukan sedemikian rupa sehingga . $f:\{0,1\}^n \to \{0,1\}^n$ $y \in \{0,1\}^n$ $x \in \{0,1\}^n$ $f(x)=y$

Jika dapat dihitung secara efisien (katakanlah, dengan sirkuit kecil), hasil Anda menyiratkan semacam solusi untuk masalah ini. $f$

$f$ $2^n$ $2^{2n/3}$ $2^{2n/3}$ $x$ $y$ $2^{2n/3}$ $2^{2n/3}$ $S$ $T$ $S \sqrt{T} = 2^n$ $f$ $f$

$f$

DW
sumber