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

20

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 P7/8+ϵ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/87/8+ϵnO(logn)2o(n)

Mohammad Al-Turkistany
fonte

Respostas:

29

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 / 87/8+ε/82O(εn)O(1/ε)εn2εn7/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 / 8ε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:2O(ε2n)

  • 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 e7/8+ε
  • a redução aumenta o tamanho da fórmula apenas por um fator .poly(1/ε)

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 ε m2O(εcm)7/8+εcε2εnεm

Ryan Williams
fonte
Graças Rayan pela sua resposta agradável, podemos tomar isso como uma evidência contra a existência de algoritmos de tempo quasi-polinomial ou sub-exponencial com rácios de aproximação melhor do que ? 7/8
Mohammad Al-Turkistany
18

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)=2n1o(1)(7/8+1/(loglogn).000001)T(n)2o(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

Ryan O'Donnell
fonte