Editing 2-satisfiability (section)

===Counting the number of satisfying assignments===
'''#2SAT''' is the problem of counting the number of satisfying assignments to a given 2-CNF formula. This [[Counting problem (complexity)|counting problem]] is [[Sharp-P-complete|#P-complete]],<ref>{{citation
 | last1 = Valiant | first1 = Leslie G. | author-link = Leslie Valiant
 | year = 1979
 | title = The complexity of enumeration and reliability problems
 | journal = [[SIAM Journal on Computing]]
 | volume=8
 | pages= 410–421
 | doi = 10.1137/0208032
 | issue = 3}}</ref> which implies that it is not solvable in [[polynomial time]] unless [[P versus NP problem|P&nbsp;=&nbsp;NP]]. Moreover, there is no [[Polynomial-time approximation scheme|fully polynomial randomized approximation scheme]] for #2SAT unless [[NP (complexity)|NP]] = [[RP (complexity)|RP]] and this even holds when the input is restricted to monotone 2-CNF formulas, i.e., 2-CNF formulas in which each [[Literal (mathematical logic)|literal]] is a positive occurrence of a variable.<ref>{{citation
 | last1 = Welsh | first1 = Dominic | author1-link = Dominic Welsh
 | last2 = Gale | first2 = Amy
 | year = 2001
 | contribution = The complexity of counting problems
 | title = Aspects of complexity: minicourses in algorithmics, complexity and computational algebra: mathematics workshop, Kaikoura, January 7–15, 2000
 | pages = 115ff}}, Theorem 57.</ref>

The fastest known algorithm for computing the exact number of satisfying assignments to a 2SAT formula runs in time <math>O(1.2377^n)</math>.<ref>{{citation|first1=Vilhelm|last1=Dahllöf|first2=Peter|last2=Jonsson|first3=Magnus|last3=Wahlström|title=Counting models for 2SAT and 3SAT formulae|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=332|issue=1–3|year=2005|pages=265–291|doi=10.1016/j.tcs.2004.10.037}}</ref>
<ref>{{citation|first1=Martin|last1=Fürer|first2=Shiva Prasad|last2=Kasiviswanathan|contribution=Algorithms for counting 2-SAT solutions and colorings with applications|title=Algorithmic Aspects in Information and Management|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=4508|year=2007|pages=47–57|doi=10.1007/978-3-540-72870-2_5|isbn=978-3-540-72868-9|citeseerx=10.1.1.634.4498}}.</ref>
<ref>{{citation|first1=Magnus|last1=Wahlström|contribution=A tighter bound for counting max-weight solutions to 2sat instances|title=International Workshop on Parameterized and Exact Computation|volume=5018|year=2008|pages=202–213|doi=10.1007/978-3-540-79723-4_19|series=Lecture Notes in Computer Science|isbn=978-3-540-79722-7|citeseerx=10.1.1.129.9232}}</ref>