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ń.
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.