论文标题
$ k $ -sat的PPSZ的较简单的部分降低
Simpler Partial Derandomization of PPSZ for $k$-SAT
论文作者
论文摘要
我们提供了最简单的$ K $ -SAT算法PPSZ [focs'97，jacm'05]的简单降低，$ k $ -sat，带有\ emph {sub-offentential}的解决方案数量。现有的derandomization使用了小样本空间的复杂构造，而我们仅使用\ emph {hashing}。我们的算法和定理也具有一个不错的副产品：当公式具有\ emph {中等指数}的解决方案数量时，它优于当前最快的确定性$ k $ -sat算法。
We give a simpler derandomization of the best known $k$-SAT algorithm PPSZ [FOCS'97, JACM'05] for $k$-SAT with \emph{sub-exponential} number of solutions. The existing derandomization uses a complicated construction of small sample space, while we only use \emph{hashing}. Our algorithm and theorem also have a nice byproduct: It outperforms the current fastest deterministic $k$-SAT algorithm when the formula has \emph{moderately exponential} number of solutions.
