The 2SAT Problem: Difference between revisions
Jump to navigation
Jump to search
| (5 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
=External= | =External= | ||
* https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem | * https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem | ||
=Internal= | =Internal= | ||
| Line 10: | Line 8: | ||
=Overview= | =Overview= | ||
=The Problem= | =The Problem= | ||
Given a set of n boolean variables x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>, that can be set to <code>true</code> or <code>false</code> and a set of m clauses of | Given a set of ''n'' boolean variables x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>, that can be set to <code>true</code> or <code>false</code> and a set of ''m'' clauses of two literals each (a "literal" is a variable or the negation of the variable: x<sub>i</sub> or !x<sub>i</sub>). The output is determining whether there is a variable assignment that simultaneously satisfies every clause. | ||
The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem. | The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem. Unlike 2SAT, the 3SAT problem is [[NP_Completeness|NP-complete]]. | ||
=Algorithms= | =Algorithms= | ||
* Reduction to computing strongly connected components. | * Reduction to computing strongly connected components. | ||
* "Backtracking" | * "Backtracking" | ||
* | * [[Papadimitriou's 2SAT Algorithm#Overview|Papadimitriou's 2SAT randomized local search]]. | ||
Latest revision as of 04:58, 30 November 2021
External
Internal
Overview
The Problem
Given a set of n boolean variables x1, x2, ..., xn, that can be set to true or false and a set of m clauses of two literals each (a "literal" is a variable or the negation of the variable: xi or !xi). The output is determining whether there is a variable assignment that simultaneously satisfies every clause.
The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem. Unlike 2SAT, the 3SAT problem is NP-complete.
Algorithms
- Reduction to computing strongly connected components.
- "Backtracking"
- Papadimitriou's 2SAT randomized local search.