Algoritmos de aproximação de tempo super polinomial para MAX 3SAT

O teorema do PCP afirma que não há algoritmo de tempo polinomial para o MAX 3SAT encontrar uma atribuição que satisfaça as cláusulas de 7/8 de uma fórmula 3SAT satisfatória, a menos que .P = N $7/8+ \epsilon$$P = NP$

Existe um algoritmo de tempo polinomial trivial que satisfaz das cláusulas. Então, podemos fazer melhor que se permitirmos algoritmos super-polinomiais? Que razões de aproximação podemos obter com algoritmos de tempo quase polinomiais ( ) ou com algoritmos de tempo subexponenciais ( )? Estou procurando referências para esses algoritmos.7 / 8 + ε n O ( log n ) 2 O ( n $7/8$$7/8+ \epsilon$$n^{O(\log n)}$$2^{o(n)}$

Pode-se obter uma aproximação de 7/8 para MAX3SAT que é executada em tempo sem muitos problemas. Aqui está a ideia. Divida o conjunto de variáveis ​​em grupos de variáveis ​​cada. Para cada grupo, tente todas as maneiras de atribuir as variáveis ​​no grupo. Para cada fórmula reduzida, execute a aproximação de Karloff e Zwick . Produza a tarefa que satisfaça um número máximo de cláusulas, em todas essas tentativas.2 O ( ε n ) S ( 1 / ε ) ε n 2 ε n 7 /$7/8+\varepsilon/8$$2^{O(\varepsilon n)}$$O(1/\varepsilon)$$\varepsilon n$$2^{\varepsilon n}$$7/8$

O ponto é que existe algum bloco variável, de modo que a atribuição ótima (restrita a esse bloco) já satisfaz uma do número máximo de cláusulas satisfeitas. Você obterá essas cláusulas extras exatamente corretas e obterá da fração restante do ideal usando Karloff e Zwick.7 /$\varepsilon$$7/8$

É uma pergunta interessante se é possível obter tempo para o mesmo tipo de aproximação. Existe uma "conjectura linear de PCP" que 3SAT pode ser reduzida em tempo polinomial para MAX3SAT, de modo que:$2^{O(\varepsilon^2 n)}$

• se a instância 3SAT for satisfatória, a instância MAX3SAT é completamente satisfatória,
• se a instância 3SAT não for satisfatória, a instância MAX3SAT não é satisfatória e$7/8+\varepsilon$
• a redução aumenta o tamanho da fórmula apenas por um fator .$poly(1/\varepsilon)$

Assumindo esta linear PCP conjectura, um -time aproximação, para todos e , implicaria que 3SAT é em tempo, para todos . (Aqui é o número de cláusulas.) A prova usa o lema da esparsificação de Impagliazzo, Paturi e Zane. 7 / 8 + ε c ε 2 ε n ε $2^{O(\varepsilon^c m)}$$7/8+\varepsilon$$c$$\varepsilon$$2^{\varepsilon n}$$\varepsilon$$m$

Para reafirmar um pouco o que Ryan Williams escreveu em seu último parágrafo:

O teorema mostra Moshkovitz-Raz que existe uma função de de tal modo que se Max-3Sat pode ser ( 7 / 8 + 1 / ( log log n ) 0,000001 ) -approximated em tempo T ( n ) então a versão de decisão do 3Sat está no tempo 2 o ( n $T(n) = 2^{n^{1-o(1)}}$$(7/8 + 1/(\log \log n)^{.000001})$$T(n)$$2^{o(n)}$. Acredita-se que o último seja impossível (essa é a hipótese do tempo exponencial), caso em que o primeiro também é impossível. Para colocá-lo não com bastante precisão, você não pode bater para Max-3Sat em qualquer coisa melhor do que tempo exponencial completo.$7/8$