Papadimitriou's 2SAT Algorithm: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
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]]

Revision as of 04:53, 30 November 2021

External

Internal

Overview

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 tow uniformly at random.
Report "unsatisfiable".

Running Time

Runs in polynomial time.