The 2SAT Problem: Difference between revisions
Jump to navigation
Jump to search
Line 17: | Line 17: | ||
* 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]] | * [[Papadimitriou's 2SAT Algorithm#Overview|Papadimitriou's 2SAT randomized local search]]. |
Revision as of 04:31, 30 November 2021
External
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/kRmJe/random-walks-on-a-line
- https://www.coursera.org/learn/algorithms-npcomplete/lecture/YltoR/analysis-of-papadimitrious-algorithm
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 2 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.
Algorithms
- Reduction to computing strongly connected components.
- "Backtracking"
- Papadimitriou's 2SAT randomized local search.