Jaka jest złożoność liczenia losowego 2-SAT?

Czy podjęto prace nad tym, jak złożoność przypadkowych instancji # 2-SAT zmienia się w zależności od gęstości klauzuli? To znaczy: w jaki sposób trudność liczenia satysfakcjonujących rozwiązań dla losowo generowanej instancji 2-SAT różni się w zależności od gęstości klauzuli? W szczególności, czy znane są rygorystyczne wyniki dotyczące progów krytycznych?

Oczywiście, ponieważ 2-SAT  ∈  P , typowa złożoność zliczania zależy częściowo od prawdopodobieństwa, z którym wystąpienie jest zadowalające; instancje, których gęstość klauzul jest wyższa niż próg krytyczny dla SAT / UNSAT, będą zazwyczaj miały łatwą liczność złożoności, ponieważ prawie na pewno odpowiedź wynosi „ zero ”, w granicy n   . Jednak złożoność zliczania może być nadal łatwa dla instancji 2-SAT o gęstości bliskiej lub nieco powyżej progu krytycznego dla skończonego n : można oczekiwać, że zadowalająca instancja będzie miała tylko niewielką liczbę rozwiązań, co może być łatwe wyliczyć ze względu na ścisłość ograniczeń.$\to \infty$

Dla k -sat z k  ≥ 3, trudność w określeniu, czy instancja jest spe lub unsatisfiable wydaje się być najwyższa w pobliżu krytycznych progów oddzielających fazy SAT od fazy UNSAT, częściowo jako ktoś próbuje ustalić, czy istnieje co najmniej jeden satysfakcjonujące rozwiązanie. W przypadku nr 2-SAT trudność nie może polegać na ustaleniu, czy istnieje przynajmniej jedno rozwiązanie; należy więc spodziewać się, że trudność prawdopodobnie będzie polegać na określeniu liczby rozwiązań dla zadowalających wzorów o znaczącej, ale nie dużej liczba ograniczeń - to znaczy tam, gdzie istnieje wystarczająca liczba ograniczeń, aby wzbudzić nietrywialne zależności między zmiennymi, ale nie tak wiele, aby przesadnie określić możliwe przypisania.

Być może ten artykuł może ci pomóc:

Nowa górna granica najgorszego przypadku dla nr 2-SAT i nr 3-SAT z liczbą klauzul jako parametrem J. Zhou, M. Yin, C. Zhou (2010).

I ten, który bada strukturę zestawu rozwiązań przypadkowej instancji 2-SAT: Satisfying Assignments of Random Boolean Constraint Problems Satisfaction: Clusters and Overlapping autorstwa G. Istrate (2007)