The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable 3-SAT formula can be found in expected running time at most O(1.3071~n). Using the technique of limited independence, we can derandomize this algorithm yielding O(1.3071~n) deterministic running time at most.
展开▼
