Derandomization of PPSZ for Unique-k-SAT
Daniel Rolf · 2005
Abstract. The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisable 3-SAT formulas can be found in expected running time at most O(1:3071n): Using the technique of limited independence, we can derandomize this algorithm yielding O(1:3071n) deterministic running time at most. 1