Papadimitriou's 2SAT Algorithm: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
|||
| (7 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 | ||
* 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= | =Internal= | ||
* [[Local_Search#Local_Search_Algorithms|Local Search]] | * [[Local_Search#Local_Search_Algorithms|Local Search]] | ||
* [[The 2SAT Problem]] | |||
=Overview= | =Overview= | ||
The algorithm performs a randomized [[Local Search|local search]]. Generally, local search heuristics are not guaranteed to run in polynomial time. The randomized local search algorithm for the 2SAT problem is one of the rare cases when we can prove it is guaranteed to converge with the correct answer quickly. | |||
=Algorithm= | |||
<font size=-1> | |||
Repeat log<sub>2</sub>n times: | |||
Choose random initial assignment | |||
Repeat 2n<sup>2</sup> times: | |||
If current assignment satisfies all clauses, halt and report. | |||
Else pick arbitrary unsatisfied clause and flip the value of one of its variables <font color=teal># choose between the two uniformly at random.</font> | |||
Report "unsatisfiable". | |||
</font> | |||
==Playground Implementation== | |||
{{External|https://github.com/ovidiuf/playground/blob/master/learning/stanford-algorithms-specialization/19-2SAT/src/main/java/playground/stanford/twosat/TwoSATInstance.java}} | |||
=Running Time= | |||
Runs in polynomial time. | |||
Latest revision as of 15:11, 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 algorithm performs a randomized local search. Generally, local search heuristics are not guaranteed to run in polynomial time. The randomized local search algorithm for the 2SAT problem is one of the rare cases when we can prove it is guaranteed to converge with the correct answer quickly.
Algorithm
Repeat log2n times:
Choose random initial assignment
Repeat 2n2 times:
If current assignment satisfies all clauses, halt and report.
Else pick arbitrary unsatisfied clause and flip the value of one of its variables # choose between the two uniformly at random.
Report "unsatisfiable".
Playground Implementation
Running Time
Runs in polynomial time.