¿Cuál es la complejidad de contar al azar 2-SAT?

¿Se ha trabajado en cómo la complejidad de las instancias aleatorias de # 2-SAT varía con la densidad de la cláusula? Es decir: ¿cómo varía la dificultad de contar soluciones satisfactorias para una instancia de 2-SAT generada aleatoriamente , a medida que varía la densidad de la cláusula? En particular, ¿se conocen resultados rigurosos que impliquen umbrales críticos?

Por supuesto, debido a que 2-SAT  ∈  P , la complejidad de conteo típica depende en parte de la probabilidad con la que una instancia es satisfactoria; Las instancias cuya densidad de cláusula está por encima del umbral crítico para SAT / UNSAT generalmente tendrán una complejidad de conteo fácil, ya que la respuesta es " cero " casi seguramente, en el límite n   . Sin embargo, la complejidad del conteo aún puede ser fácil para instancias de 2-SAT que tienen una densidad cercana o justo por encima del umbral crítico para n finito : uno podría esperar que una instancia satisfactoria tenga solo un pequeño número de soluciones, lo que podría ser fácil enumerar debido a la rigidez de las restricciones.$\to \infty$

Para k -SAT con k  ≥ 3, la dificultad de determinar si una instancia es satisfactoria o insatisfactoria parece ser mayor cerca de los umbrales críticos que separan la fase SAT de la fase UNSAT, en parte porque uno trata de determinar si existe al menos uno solución satisfactoria Para # 2-SAT , la dificultad no puede estar en determinar si existe al menos una solución; Por lo tanto, uno debe esperar que la dificultad sea determinar el número de soluciones para fórmulas satisfactorias de un nivel significativo pero no grande cantidad de restricciones, es decir, cuando hay suficientes restricciones para inducir dependencias no triviales entre variables, pero no tantas como para sobredeterminar las posibles asignaciones.

Quizás este documento te pueda ayudar:

Nuevo límite superior de peor caso para # 2-SAT y # 3-SAT con el número de cláusulas como parámetro por J. Zhou, M. Yin, C. Zhou (2010).

Y este que estudia la estructura del conjunto de soluciones de una instancia aleatoria de 2-SAT: Asignaciones satisfactorias de problemas de satisfacción de restricciones booleanas aleatorias: agrupaciones y superposiciones por G. Istrate (2007)