Tamaños de PCP asintóticos más conocidos / 3-SAT

¿Cuáles son los límites superiores asintóticos más conocidos en tamaños de pruebas probabilísticamente comprobables? Idealmente, estoy buscando una encuesta contemporánea sobre esta amplia pregunta, pero si no hay ninguna, estoy especialmente interesado en la inaccesibilidad de 3-SAT.

Deje que 7/8 + ε-3-SAT sea 3-SAT con la promesa de que si la fracción 7/8 + ε de las cláusulas es satisfactoria, entonces la instancia es satisfactoria. ¿Cuáles son las reducciones más conocidas de 3-SAT con cláusulas a 7/8 + ε-3-SAT? Por ejemplo, ¿hay una reducción usando las cláusulas ? ( cláusulas es un problema abierto). ¿Una reducción en el tamaño cuasilineal uniforme NC? ¿Cuál es la dependencia de , incluso cuando ? ¿Existe un tamaño lineal conocido (dependiente de ) de reducción de (1-ε) -3-SAT a 7/8 + ε-3-SAT, y si no, tenemos mejores límites para (1-ε) -3 -¿SE SENTÓ? Incluso una respuesta parcial sería interesante. $n$ $O(n \log n)$ $O(n)$ $ε$ $ε→0$ $ε$

Además, aunque quizás haría la pregunta demasiado amplia, debo mencionar que otro tema importante aquí son los factores constantes, que debido a técnicas como el código largo son comúnmente inviablemente grandes.

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

Respuestas:

El estado de la técnica para PCP que produce una reducción a 3-SAT (incluso para sub-constante ) son las de Dana Moshkovitz y Ran Raz , que tener longitud . Sin embargo, no sé si alguien intentó calcular la dependencia exacta de la longitud de , o la complejidad de cálculo de la reducción. Su resultado técnico principal fue simplificado más tarde por Irit Dinur y Prahladh Harsha . $(\frac{7}{8}+\varepsilon)$ $\varepsilon$ $n^{1 + o(1)}$ $\varepsilon$

Si está interesado en PCP cortos con un número constante de consultas que no necesariamente ofrecen reducciones óptimas de dureza de aproximación (también conocido como "PCP de alto error"), entonces el resultado más avanzado es PCP de longitud debido a Eli Ben-Sasson y Madhu Sudán y su mejora por Dinur . Nuevamente, no sé si alguien cuál es la complejidad exacta de calcular la reducción. $n\cdot \mathrm{poly}\log n$

O meir
fuente

Gracias; Ambas partes fueron útiles. Supongo que PCP de tamaño cuasilineal con consultas O (1) y error constante sigue siendo un problema abierto.

Dmytro Taranovsky

No, eso en realidad se desprende del trabajo de Ben-Sasson y Sudán. Es un problema abierto obtener tales PCP con un error subconstante.

O Meir el

Miré un poco más y Dinur 2007 extiende el documento que citó en el segundo párrafo para mostrar . Si entiendo correctamente, esto implica una reducción de 3-SAT a algún tamaño cuasilineal 3-SAT, pero el resultado que citó en el primer párrafo no es redundante porque nos da 7/8 y más.

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+ε$

Dmytro Taranovsky

Si eso es correcto. Olvidé mencionar el resultado de Dinur, lo agregaré a la respuesta.

O Meir el