Qual é a complexidade da contagem aleatória de 2-SAT?

18

Foi realizado algum trabalho sobre como a complexidade das instâncias aleatórias do # 2-SAT varia com a densidade da cláusula? Ou seja: como a dificuldade de contar soluções satisfatórias para uma instância gerada aleatoriamente de 2-SAT varia, conforme a densidade da cláusula varia? Em particular, existem resultados rigorosos conhecidos envolvendo limites críticos?

Obviamente, devido ao 2-SAT  ∈  P , a complexidade típica da contagem depende em parte da probabilidade com que uma instância é satisfatória; instâncias cuja densidade de cláusulas está acima do limite crítico para SAT / UNSAT normalmente terão uma complexidade de contagem fácil, pois a resposta é " zero " quase certamente, no limite n  . No entanto, a complexidade da contagem ainda pode ser fácil para instâncias do 2-SAT com densidade próxima ou acima do limite crítico para n finito : pode-se esperar que uma instância satisfatória tenha apenas um pequeno número de soluções, o que pode ser fácil enumerar devido à rigidez das restrições.

Para k -SAT com k  ≥ 3, a dificuldade de determinar se uma instância é satisfatória ou insatisfatória parece ser mais alta perto dos limites críticos que separam a fase SAT da fase UNSAT, em parte quando se tenta determinar se existe pelo menos um. solução satisfatória. Para # 2-SAT , a dificuldade não pode estar em determinar se pelo menos uma solução existe; portanto, é de se esperar que a dificuldade seja provavelmente a de determinar o número de soluções para fórmulas satisfatórias de um valor significativo, mas não grande. número de restrições - isto é, onde existem restrições suficientes para induzir dependências não triviais entre variáveis, mas não tantas que superestimam as possíveis atribuições.

Niel de Beaudrap
fonte
2
Boa pergunta. Não é uma resposta, mas é interessante que, para o problema de decisão do 3-SAT, o limiar de dureza esteja em torno de m / n = 4,26 (o mesmo local do limiar de satisfação), enquanto que para o # 3-SAT é em torno de 1,5 (consulte Manual de satisfação) ou) Portanto, mesmo para o limite de dureza da complexidade da contagem está longe do limite de decisão. Eu estaria interessado em ver se algum trabalho rigoroso foi feito para o k geral. k3
Huck Bennett

Respostas: