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

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.$\to \infty$

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.

Talvez este documento possa ajudá-lo:

Novo limite superior de pior caso para # 2-SAT e # 3-SAT com o número de cláusulas como parâmetro por J. Zhou, M. Yin, C. Zhou (2010).

E este que estuda a estrutura do conjunto de soluções de uma instância aleatória de 2-SAT: Satisfação de atribuições de problemas aleatórios de satisfação de restrições booleanas: clusters e sobreposições de G. Istrate (2007)