Papadimitriou's 2SAT Algorithm: Difference between revisions
Jump to navigation
Jump to search
| Line 6: | Line 6: | ||
=Overview= | =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. | |||
Revision as of 04:32, 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.