A Satisfiability algorithm for propositional 3CNF formulas via random walks




We will discuss Schoening's randomized algorithm for the
NP-complete 3CNFSAT problem. The algorithm is based on random walks
and it runs in time poly(n)(4/3)^n, where n is the number of Boolean
variables in the formula. The talk will be entirely self-contained and will,
in particular, include necessary basics on random walks.