Ukuran PCP asimptotik paling dikenal / 3-SAT

Apa batas atas asimptotik yang paling dikenal pada ukuran bukti yang dapat diperiksa secara probabilistik? Idealnya, saya mencari survei kontemporer tentang pertanyaan luas ini, tetapi jika tidak ada, saya terutama tertarik pada ketidak-taksiran 3-SAT.

Misalkan 7/8 + ε-3-SAT menjadi 3-SAT dengan janji bahwa jika fraksi 7/8 + ε dari klausa tersebut memuaskan, maka instance tersebut memuaskan. Apa pengurangan 3-SAT yang paling dikenal dengan $n$ klausa menjadi 7/8 + ε-3-SAT? Misalnya, apakah ada pengurangan menggunakan klausa $O(n \log n)$ ? ( $O(n)$ klausa adalah masalah terbuka.) Pengurangan dalam ukuran quasilinear NC yang seragam? Apa ketergantungan pada $ε$ , termasuk kapan $ε→0$ ? Apakah ada ukuran linier yang diketahui (tergantung pada $ε$ ) pengurangan (1-ε) -3-SAT menjadi 7/8 + ε-3-SAT, dan jika tidak, apakah kita memiliki batasan yang lebih baik untuk (1-ε) -3-SAT? Bahkan sebagian jawaban akan menarik.

Juga, sementara itu mungkin akan membuat pertanyaan terlalu luas, saya harus menyebutkan bahwa masalah penting lainnya di sini adalah faktor konstan, yang karena teknik seperti kode panjang biasanya sangat besar.

cc.complexity-theory reference-request np-hardness pcp Dmytro Taranovsky
sumber

Jawaban:

$(\frac{7}{8}+\varepsilon)$ $\varepsilon$ $n^{1 + o(1)}$ $\varepsilon$

$n\cdot \mathrm{poly}\log n$

Atau Meir
sumber

Terima kasih; kedua bagian itu membantu. Saya mengumpulkan bahwa PCP ukuran quasilinear dengan O (1) pertanyaan dan kesalahan konstan tetap merupakan masalah terbuka.

Dmytro Taranovsky

Tidak, itu sebenarnya berasal dari karya Ben-Sasson dan Sudan. Ini adalah masalah terbuka untuk mendapatkan PCP seperti itu dengan kesalahan sub-konstan.

Atau Meir

S A T \in P C P_{\frac{1}{2}, 1} [\log_{2} n + O (\log \log n), O (1)]

$SAT ∈ PCP_{\frac{1}{2},1}[\log_2 n + O(\log \log n), O(1)]$

1 - ε

$1-ε$

7 / 8 + ε

$7/8+ε$

Ya itu benar. Saya lupa menyebutkan hasil Dinur, saya akan menambahkannya ke jawabannya.

Atau Meir