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 ϵ
Editar nota: Substituiu por para esclarecer a confusão.£ ( n )
cc.complexity-theory
ds.algorithms
sat
np
Rafi Witten
fonte
fonte
Respostas:
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<ϵ<1 1/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 .SS S
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 SS S S
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
fonte