Condições para tratabilidade da Satisfação 3SAT

12

O que estou pensando especificamente é se existe uma condição interessante na porcentagem de tarefas que atendem à fórmula 3SAT para garantir que esses problemas sejam tratáveis.

Suponha, por exemplo, a classe de problemas 3SAT que das atribuições possíveis satisfazem a fórmula booleana; podemos encontrar com eficiência uma tarefa satisfatória? Para qual é o problema resultante em P?2 n ϵϵ(n)2n2nϵ

Editar nota: Substituiu por para esclarecer a confusão.£ ( n )ϵϵ(n)

Rafi Witten
fonte
4
Uma observação simples: se é no máximo polinomialmente inverso, a amostragem uniforme de vezes produzirá uma solução no tempo polinomial esperado. Portanto, se está entre 1 e 1 / poly (n), esse problema é fácil (está no ZPP). 1 / ϵ ϵϵ1/ϵϵ
22610 Robin Ontário
1
Da mesma forma, se 1 / eps é quasipolynomial, então você tem um algoritmo de tempo quasipoly randomizados, que em si seria surpreendente
Suresh Venkat

Respostas:

12

Sim. Se for uma constante (ou ), e você prometeu que pelo menos de todas as atribuições possíveis estão satisfazendo os 3CNFs de entrada, você pode encontrar tal atribuição em tempo polinomial determinístico .1 / polilog ( n ) ϵ 2 n0<ϵ<11/polylog(n)ϵ2n

Os algoritmos não são difíceis:

Reivindicação: Sob a promessa foi dito, deve existir um tamanho constante conjunto de variáveis que atinge todas as cláusulas do 3CNF, no sentido de que todos os 3 cláusula deve conter uma variável de .SSS

Prova de reivindicação (esboço): Caso contrário, deve existir uma família suficientemente grande de 3 cláusulas do 3CNF, na qual cada variável ocorre apenas uma vez. Mas essa família, quando suficientemente grande, já possui menos de fração de tarefas satisfatórias. QEDϵ

Assim, você pode executar mais possível (número constante) de atribuições para . Sob todas as atribuições fixas a , o 3CNF se torna um 2CNF, supondo que atinja o 3CNF original. Agora, você pode usar o algoritmo determinístico polytime conhecido para encontrar uma atribuição satisfatória para as fórmulas 2CNF. No geral, você obtém um limite superior de tempo polinomial.S SSSS

Acho que o algoritmo para o 2SAT já está no famoso artigo de S. Cook de 1971.

O algoritmo para 3CNFs é de: L. Trevisan Uma nota sobre a contagem aproximada determinística para k-DNF In Proc. de APPROX-RANDOM, Springer-Verlag, página 417-426, 2004

O artigo original que mostra o resultado do 3CNF é: E. Hirsch, Um algoritmo determinístico rápido para fórmulas com muitas atribuições satisfatórias , Journal of the IGPL, 6 (1): 59-71, 1998

Iddo Tzameret
fonte
Obrigado pela resposta. Na verdade, eu estava interessado em não constante, mas aprender a existência de um algoritmo determinístico é interessante. Editei a pergunta para torná-la mais clara. ϵ
Rafi Witten
1
@ Rafi, acho que o mesmo algoritmo funciona para não constante . ϵ=1/polylog(n)
Iddo Tzameret
Como você constrói S?
Radu Grigore
1
@ Radu, acho que você pode fazer isso com avidez: escolha uma primeira cláusula arbitrária . Em seguida, escolha outra cláusula cujas variáveis ​​não sejam de . Continue fazendo isso, até que você não consiga encontrar uma cláusula com variáveis ​​disjuntas para as cláusulas que você já escolheu. Portanto, as variáveis ​​nas cláusulas que você escolheu são o conjunto de ocorrências. C 2 C 1C1C2C1
Idd Tzameret 19/11/2010