Editing 2-satisfiability (section)

===Maximum-2-satisfiability ===<!-- MAX-2-SAT redirects here -->
In the maximum-2-satisfiability problem ('''MAX-2-SAT'''), the input is a formula in [[conjunctive normal form]] with two [[Literal (mathematical logic)|literals]] per clause, and the task is to determine the maximum number of clauses that can be simultaneously satisfied by an assignment. Like the more general [[maximum satisfiability problem]], MAX-2-SAT is [[NP-hard]]. The proof is by reduction from [[Boolean satisfiability problem|3SAT]].<ref>{{citation|year=1976|author1=M. R. Garey|author2=D. S. Johnson|author3=L. J. Stockmeyer|title=Some simplified NP-complete graph problems|journal=Theoretical Computer Science|language=en|volume=1|issue=3|pages=237–267|doi=10.1016/0304-3975(76)90059-1|issn=0304-3975}}; see pp. 4–6</ref>

By formulating MAX-2-SAT as a problem of finding a [[Cut (graph theory)|cut]] (that is, a partition of the vertices into two subsets) maximizing the number of edges that have one endpoint in the first subset and one endpoint in the second, in a graph related to the implication graph, and applying [[semidefinite programming]] methods to this cut problem, it is possible to find in polynomial time an approximate solution that satisfies at least 0.940... times the optimal number of clauses.<ref>{{citation|first1=Michael|last1=Lewin|first2=Dror|last2=Livnar|first3=Uri|last3=Zwick|author3-link=Uri Zwick|contribution=Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems|title=Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization|year=2002|pages=67–82|isbn=978-3-540-43676-8|publisher=Springer-Verlag}}</ref> A ''balanced'' MAX 2-SAT instance is an instance of MAX 2-SAT where every variable appears positively and negatively with equal weight. For this problem, Austrin has improved the approximation ratio to <math>\min \left\{(3 - \cos \theta)^{-1} (2 + (2/\pi)\theta) \,:\, \pi/2 \leq \theta \leq \pi \right\} = 0.943...</math>.<ref>{{citation
 | last = Austrin | first = Per
 | contribution = Balanced Max 2-sat Might Not Be the Hardest
 | doi = 10.1145/1250790.1250818
 | isbn = 978-1-59593-631-8
 | location = New York, NY, USA
 | pages = 189–197
 | publisher = ACM
 | title = Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (STOC '07)
 | year = 2007| s2cid = 2353625
 }}.</ref>

If the [[unique games conjecture]] is true, then it is impossible to approximate MAX 2-SAT, balanced or not, with an [[approximation ratio|approximation constant]] better than 0.943... in polynomial time.<ref>{{citation|first1=Subhash|last1=Khot|author1-link=Subhash Khot|first2=Guy|last2=Kindler|first3=Elchanan|last3=Mossel|first4=Ryan|last4=O'Donnell| author4-link = Ryan O'Donnell (computer scientist)|contribution=Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?|title=FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science|year=2004|pages=146–154|doi=10.1109/FOCS.2004.49|isbn=978-0-7695-2228-9|publisher=IEEE|citeseerx=10.1.1.126.2295|s2cid=2090495}}</ref> Under the weaker assumption that [[P versus NP problem|P&nbsp;≠&nbsp;NP]], the problem is only known to be inapproximable within a constant better than 21/22 = 0.95454...<ref>{{citation|first=Johan|last=Håstad|author-link=Johan Håstad|title=Some optimal inapproximability results|journal=[[Journal of the ACM]]|volume=48|issue=4|year=2001|pages=798–859|doi=10.1145/502090.502098|citeseerx=10.1.1.638.2808|s2cid=5120748}}.</ref>

Various authors have also explored exponential worst-case time bounds for exact solution of MAX-2-SAT instances.<ref>{{citation|first1=N.|last1=Bansal|first2=V.|last2=Raman|contribution=Upper bounds for MaxSat: further improved|editor1-first=A.|editor1-last=Aggarwal|editor2-first=C.|editor2-last=Pandu Rangan|title=Proc. 10th Conf. Algorithms and Computation, ISAAC'99|series=Lecture Notes in Computer Science|volume=1741|publisher=Springer-Verlag|year=1999|pages=247–258}}; {{citation|first1=Jens|last1=Gramm|first2=Edward A.|last2=Hirsch|first3=Rolf|last3=Niedermeier|first4=Peter|last4=Rossmanith|author3-link=Rolf Niedermeier|title=Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT|journal=[[Discrete Applied Mathematics]]|volume=130|issue=2|year=2003|pages=139–155|doi=10.1016/S0166-218X(02)00402-X}}; {{citation|first1=Arist|last1=Kojevnikov|first2=Alexander S.|last2=Kulikov|contribution=A new approach to proving upper bounds for MAX-2-SAT|title=Proc. 17th ACM-SIAM Symp. Discrete Algorithms|year=2006|pages=11–17|doi=10.1145/1109557.1109559|isbn=978-0-89871-605-4|s2cid=10194873}}</ref>