Blog
2-SAT - a randomized algorithm
2009-08-09 13:14:40As everybody knows, SAT is NP-complete. However, a 2-SAT-instance can be solved with a randomized algorithm.
Here is a randomized algorithm that (eventually) solves an instance of a 2-SAT-Problem (in polynomial time).
read on