Masalah Penguji (pembuatan contoh / jawaban keputusan SAT yang seragam)

Asisten mengajar mata kuliah telah berhasil menulis sebuah program yang (secara deterministik) menghasilkan pertanyaan-pertanyaan ujian yang sulit. Sekarang, dia ingin menulis sebuah program yang menghasilkan jawaban yang sesuai. Masalah Penguji menanyakan apakah ini selalu mungkin; yang Pemeriksa Dugaan menyatakan bahwa, dengan asumsi, , itu tidak : datang dengan masalah ini lebih mudah daripada datang dengan solusi mereka.$\mathsf{P} \neq \mathsf{NP}$

Lebih formal, misalkan menjadi Mesin Turing deterministik yang, pada input 1 n , menghasilkan dalam waktu polinomial formula Boolean ukuran n . Saya ingin tahu apakah, untuk semua M seperti itu , terdapat mesin Turing polinomial waktu deterministik M ′ yang, pada input 1 n , menghasilkan " 1 " jika M ( 1 n ) memiliki tugas yang memuaskan dan " 0 " jika tidak .$M$$1^n$$n$$M$$M'$$1^n$$1$$M(1^n)$$0$

Dengan asumsi , apakah pertanyaan ini sudah ditanyakan atau dijawab? Jika tidak dijawab, asumsi tambahan macam apa ( mis. Fungsi satu arah?) Yang mungkin terjadi pada hasilnya? Kecuali salah satu di atas, "dugaan" saya adalah bahwa "jawab" TM tidak selalu ada, tetapi apa intuisi Anda?$\mathsf{P} \neq \mathsf{NP}$

Terima kasih!

Pertanyaan yang Anda ajukan setara dengan NP unary = unary P, yang pada gilirannya setara dengan NE = E, oleh padding.

Dari judul, mungkin Anda bermaksud bertanya apakah mungkin untuk menghasilkan pasangan input / output sedemikian rupa sehingga distribusi pada input tersebut "sulit." Kemungkinan melakukan ini terletak di suatu tempat antara P NP dan fungsi satu arah ada.$\ne$

Dalam model komputasi terbatas, diketahui bahwa ini mungkin. Misalnya seseorang dapat menghasilkan pasangan input / output untuk fungsi paritas atau mayoritas di AC 0 atau di bawah. Lihat Kompleksitas distribusi .$^0$

Pertanyaan: Biarkan menghasilkan formula. Apakah { M ( 1 n ) ∣ n ∈ N ∧ M ( 1 n ) ∈ S A T } milik P ?$M\in \mathsf{PF}$$\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$$\mathsf{P}$

$succinctSAT \in \mathsf{E} \implies$ Iya:

Asumsi tentang pembuatan rumus dalam waktu polinomial dari berarti bahwa rumus tersebut dapat diberikan secara ringkas . Anda ingin menentukan kepuasan mereka dalam waktu n O ( 1 ) .$1^n$$n^{O(1)}$

Dengan kita dapat menemukan n dalam waktu polinomial dalam | φ | . Kemudian φ dapat dinyatakan secara singkat dalam lg n + O ( 1 ) bit menggunakan M dan n . Kita dapat menggunakan kami s u c c i n t S A T algoritma dalam E untuk memutuskan ini dalam waktu 2 O ( lg n ) = n $\varphi = M(1^n)$$n$$|\varphi|$$\varphi$$\lg n+O(1)$$M$$n$$succintSAT$$\mathsf{E}$ .$2^{O(\lg n)} = n^{O(1)}$

Iya :$\implies succinctSAT \in \mathsf{E}$

Biarkan st memberikan sirkuit C di unary , M menghitung string dengan ringkas yang dikodekan oleh C , dan mengembalikan hasilnya jika itu adalah rumus dan ⊥ jika tidak.$M \in \mathsf{PF}$$C$$M$$C$$\bot$

Asumsikan bahwa milik P . Untuk mengatasi s u c c i n c t S A T kita menulis rumus singkat yang diberikan di unary dan kemudian menggunakan asumsi kita untuk menyelesaikannya.$\{ M(1^n) \mid n\in \mathbb{N} \land M(1^n)\in SAT\}$$\mathsf{P}$$succinctSAT$

Pertanyaan: Bisakah kita menghasilkan pasangan solusi-waktu polinomial-waktu untuk sehingga turunannya sulit?$SAT$

Kita harus mengklarifikasi apa yang kita maksud dengan instance menjadi sulit karena instance apa pun dengan sendirinya (secara teoritis) mudah karena dapat diselesaikan dengan algoritma yang selalu mengatakan ya atau algoritma yang selalu mengatakan tidak. Tampak bagi saya bahwa Anda mencoba untuk mengatasi masalah ini dengan memaksakan keseragaman. Berpikir dalam istilah kriptografis, tanpa beberapa informasi yang tidak diungkapkan kepada musuh, tidak ada gunanya menyembunyikan sisa perhitungan karena musuh dapat mensimulasikan protokol.

Asumsikan bahwa kita memiliki algoritma waktu polinomial yang menghasilkan pasangan solusi-instan. Musuh dapat menggunakan algoritma yang sama untuk menemukan jawabannya jika ia tahu dan menemukan n tidak sulit dari rumus. Cara yang lebih masuk akal adalah dengan menggunakan kunci rahasia yang dipilih secara acak untuk mengatasi ini dan mengendurkan kondisi kekerasan menjadi probabilistik: tidak ada algoritma waktu polinomial yang dapat menemukan solusi dengan probabilitas tinggi (tanpa mengetahui kunci rahasia).$n$$n$

Apakah ada yang efisien (deterministik) algoritma sehingga diberi dipilih secara acak k ∈ { 0 , 1 } n , menghasilkan sepasang dari SAT contoh φ k dan jawabannya w k sehingga tidak ada yang efisien (probabilistik / seragam) algoritma musuh D dapat dengan benar memecahkan instance SAT yang dihasilkan oleh A dengan probabilitas yang tidak dapat diabaikan?$A$
$k \in \{0,1\}^n$
$\varphi_k$$w_k$
$D$
$A$

Atau lebih formal,

Apakah ada sehingga untuk semua D ∈ P / p o l y , sehingga S A T ( A ( k ) 1 ) = A ( k ) 2 untuk semua k dan P r k ∈ { 0 , 1 } n { D ( A ( k ) 1 ) = S A $A\in \mathsf{PF}$$D \in \mathsf{P/poly}$$SAT(A(k)_1) = A(k)_2$$k$

$$\mathsf{Pr}_{k \in \{0,1\}^n} \{ D(A(k)_1) = SAT(A(K)_1) \} < \frac{1}{poly(n)}$$

Mudah untuk melihat bahwa fungsi seperti itu dapat diubah menjadi fungsi satu arah seolah-olah mudah untuk menemukan dari φ k maka kita dapat menemukan jawabannya dengan menghitung A ( k ) 2 .$k$$\varphi_k$$A(k)_2$

Di sisi lain, biarkan menjadi fungsi satu arah. Kita dapat menyatakan f ( x ) = y sebagai sirkuit ukuran polinomial karena f dapat dihitung dalam waktu polinomial (dan kita dapat mengubahnya menjadi rumus dengan memperkenalkan variabel baru untuk semua gerbang dan secara lokal menegakkan kondisi untuk kebenaran perhitungan) seperti dalam terjemahan Tsien). Mari kita anggap y sebagai parameter dan tunjukkan rumus yang dihasilkan sebagai φ f , y ( x ) . Kita dapat bertanya apakah ada x yang memenuhi φ f , y ( x $f$$f(x)=y$$f$$y$$\varphi_{f,y}(x)$$x$$\varphi_{f,y}(x)$. Algoritma waktu polinomial apa pun yang memecahkan instance dengan probabilitas yang tidak dapat diabaikan akan memecah fungsi satu arah f . Namun ini menggunakan fakta bahwa musuh perlu menemukan saksi bukan hanya fakta bahwa formula itu memuaskan atau tidak (tapi saya pikir kita bisa menyelesaikan masalah ini dengan menggunakan hard-bit f ).$SAT$$f$$f$

Lihat juga bab 29 dan 30 buku Jan Krajicek "Memaksa dengan Variabel Acak", 2011 tentang generator kompleksitas bukti .