Derandomization of PPSZ for Unique- k-SAT
Derandomization of PPSZ for Unique- k-SAT
复制标题
Unique-k-SAT 的 PPSZ 去随机化
DOI：
10.1007/11499107_16
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Daniel Rolf
中科院分区：
文献类型：
--
作者：
Daniel Rolf
Paturi，Pudlak，Saks，和赞内在1998年提出的PPSZ算法具有一个很好的特点，即在期望运行时间内最多可以找到$\mathcal{O}（1.3071^n）$唯一满足的3-SAT公式的唯一满意解。使用有限独立的技术，我们可以去随机化这个算法产生$\mathcal{O}（1.3071^n）$确定性的运行时间。
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 $\mathcal{O}(1.3071^n)$. Using the technique of limited independence, we can derandomize this algorithm yielding $\mathcal{O}(1.3071^n)$ deterministic running time at most.