Tamanhos PCP assintóticos mais conhecidos / 3-SAT

Quais são os limites superiores assintóticos mais conhecidos em tamanhos de provas probabilisticamente verificáveis? Idealmente, estou procurando uma pesquisa contemporânea sobre essa ampla questão, mas, se não houver, estou especialmente interessado na falta de aproximação do 3-SAT.

Seja 7/8 + ε-3-SAT com 3-SAT com a promessa de que, se a fração 7/8 + ε das cláusulas for satisfatória, a instância será satisfatória. Quais são as reduções mais conhecidas de 3-SAT com $n$ cláusulas para 7/8 + ε-3-SAT? Por exemplo, há uma redução usando cláusulas $O(n \log n)$ ? ( $O(n)$ cláusulas é um problema em aberto.) Uma redução no tamanho quase-uniforme NC? Qual é a dependência de , incluindo quando ? Existe uma redução conhecida do tamanho linear (dependente de ) da redução de (1-ε) -3-SAT para 7/8 + ε-3-SAT; caso contrário, temos limites melhores para (1-ε) -3 -SENTOU? Mesmo uma resposta parcial seria interessante. $ε$ $ε→0$ $ε$

Além disso, embora isso talvez torne a questão muito ampla, devo mencionar que outra questão importante aqui são os fatores constantes, que devido a técnicas como o código longo geralmente são incomensuravelmente grandes.

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

Respostas:

O estado da arte para PCPs que produzem uma redução para 3-SAT (mesmo para sub-constante ) são os de Dana Moshkovitz e Ran Raz , que tem comprimento . No entanto, não sei se alguém tentou calcular a dependência exata do comprimento em ou a complexidade computacional da redução. Seu principal resultado técnico foi simplificado posteriormente por Irit Dinur e Prahladh Harsha . $(\frac{7}{8}+\varepsilon)$ $\varepsilon$ $n^{1 + o(1)}$ $\varepsilon$

Se você estiver interessado em PCPs curtos com um número constante de consultas que não fornecem necessariamente reduções ideais de dureza de aproximação (também conhecidas como "PCPs com alto erro"), o resultado da última geração é PCPs de comprimento devido a Eli Ben-Sasson e Madhu Sudan e sua melhoria por Dinur . Novamente, não sei se alguém qual é a complexidade exata de calcular a redução. $n\cdot \mathrm{poly}\log n$

Ou Meir
fonte

Obrigado; ambas as partes foram úteis. Entendo que o PCP de tamanho quase-linear com consultas O (1) e erro constante continuam sendo um problema em aberto.

Dmytro Taranovsky

Não, isso realmente decorre do trabalho de Ben-Sasson e Sudão. É um problema em aberto obter tais PCPs com erro sub constante.

Ou Meir

Procurei um pouco mais e o Dinur 2007 estende o artigo que você citou no segundo parágrafo para mostrar . Se bem entendi, isso implica uma redução de 3-SAT para um tamanho quase linear 3-SAT, mas o resultado que você citou no primeiro parágrafo não é redundante porque nos fornece 7/8 e mais.

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

Sim esta correto. Esqueci de mencionar o resultado de Dinur, vou adicioná-lo à resposta.

Ou Meir