Editing 2-satisfiability (section)

===Random 2-satisfiability instances===

One can form a 2-satisfiability instance at random, for a given number ''n'' of variables and ''m'' of clauses, by choosing each clause uniformly at random from the set of all possible two-variable clauses. When ''m'' is small relative to ''n'', such an instance will likely be satisfiable, but larger values of ''m'' have smaller probabilities of being satisfiable. More precisely, if ''m''/''n'' is fixed as a constant α ≠ 1, the probability of satisfiability tends to a [[Limit of a sequence|limit]] as ''n'' goes to infinity: if α&nbsp;&lt;&nbsp;1, the limit is one, while if α&nbsp;&gt;&nbsp;1, the limit is zero. Thus, the problem exhibits a [[phase transition]] at α&nbsp;=&nbsp;1.<ref>{{citation|first1=Béla|last1=Bollobás|author1-link=Béla Bollobás|first2=Christian|last2=Borgs|first3=Jennifer T.|last3=Chayes|author3-link=Jennifer Tour Chayes|first4=Jeong Han|last4=Kim|first5=David B.|last5=Wilson|title=The scaling window of the 2-SAT transition|journal=Random Structures and Algorithms|volume=18|issue=3|pages=201–256|year=2001|doi=10.1002/rsa.1006|arxiv=math/9909031|s2cid=9954684}}; {{citation|first1=V.|last1=Chvátal|author-link1=Václav Chvátal|first2=B.|last2=Reed|title=Proceedings., 33rd Annual Symposium on Foundations of Computer Science |author2-link=Bruce Reed (mathematician)|contribution=Mick gets some (the odds are on his side)|year=1992|pages=620–627|doi=10.1109/SFCS.1992.267789|isbn=978-0-8186-2900-6|s2cid=5575389}}; {{citation|first=A.|last=Goerdt|title=A threshold for unsatisfiability|journal=[[Journal of Computer and System Sciences]]|volume=53|year=1996|pages=469–486|doi=10.1006/jcss.1996.0081|issue=3|doi-access=free}}.</ref>