Tamanhos PCP assintóticos mais conhecidos / 3-SAT

9

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(nlogn) ? ( O(n) cláusulas é um problema em aberto.) Uma redução no tamanho quase-uniforme NC? Qual é a dependência de , incluindo quando ε → 0 ? 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.

Dmytro Taranovsky
fonte

Respostas:

7

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 .(78+ε)εn1+o(1)ε

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.npolylogn

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
11
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. SATPCP12,1[log2n+O(loglogn),O(1)]1ε7/8+ε
Dmytro Taranovsky
Sim esta correto. Esqueci de mencionar o resultado de Dinur, vou adicioná-lo à resposta.
Ou Meir