Какова сложность подсчета случайных 2-SAT?

Была ли проделана какая-либо работа над тем, как сложность случайных экземпляров # 2-SAT зависит от плотности предложения? То есть: как изменяется сложность подсчета удовлетворяющих решений для случайно сгенерированного экземпляра 2-SAT , когда меняется плотность предложений? В частности, известны ли какие-либо строгие результаты, касающиеся критических порогов?

Конечно, поскольку 2-SAT  ∈  P , типичная сложность счета частично зависит от вероятности, с которой экземпляр является выполнимым; экземпляры, у которых плотность предложений выше критического порога для SAT / UNSAT , как правило, будут иметь сложность подсчета, поскольку ответ почти наверняка равен « нулю » в пределе n  . Однако сложность подсчета все еще может быть легкой для случаев, когда 2-SAT имеет плотность, близкую или чуть превышающую критический порог для конечного n : можно ожидать, что удовлетворительный экземпляр будет иметь только небольшое количество решений, что может быть легко перечислять из-за жесткости ограничений.$\to \infty$

Для k -SAT с k  ≥ 3 трудность определения того, является ли экземпляр удовлетворительным или неудовлетворительным, кажется наиболее высокой вблизи критических порогов, отделяющих фазу SAT от фазы UNSAT, частично потому, что каждый пытается определить, существует ли хотя бы один удовлетворительное решение. Для # 2-SAT трудность не может заключаться в определении, существует ли хотя бы одно решение; поэтому следует ожидать, что сложность, вероятно, заключается в определении числа решений для выполнимых формул значительного, но не большого количество ограничений - то есть там, где имеется достаточно ограничений, чтобы вызвать нетривиальные зависимости между переменными, но не так много, чтобы переопределить возможные назначения.

Возможно, эта статья поможет вам:

Новая верхняя граница наихудшего случая для # 2-SAT и # 3-SAT с количеством пунктов в качестве параметра. Автор: J. Zhou, M. Yin, C. Zhou (2010).

И это тот, который изучает структуру множества решений случайного экземпляра 2-SAT: Удовлетворение назначений случайных логических проблем удовлетворенности: кластеры и перекрытия по Г. Истрате (2007)