论文标题
PPSZ比您想象的要好
PPSZ is better than you think
论文作者
论文摘要
长期以来，PPSZ是$ k $ -sat的最快已知算法，通过以随机顺序浏览输入公式的变量来工作；然后将每个变量随机设置为$ 0 $或$ 1 $，除非可以通过有效实现的规则（例如小宽度分辨率；或一小部分条款）推断出正确的值。我们证明，PPSZ的性能比以前所知的，所有$ k \ geq 3 $都要好。对于独特的$ 3 $ -SAT，我们以$ O（1.306973^{n}）$将其运行时间绑定，它比Hansen，Kaplan，Zamir和Zwick的算法好一些，该算法在时间$ o（1.306995^n）$中运行。在此之前，最著名的上限以唯一的-3 $ -sat为$ O（1.3070319^n）$。在不更改原始PPSZ的情况下实现了所有改进。核心思想是假装PPSZ不会以统一的随机顺序处理变量，而是根据精心设计的分布。我们写“假装”，因为这可以在没有对算法的任何实际更改的情况下完成。
PPSZ, for long time the fastest known algorithm for $k$-SAT, works by going through the variables of the input formula in random order; each variable is then set randomly to $0$ or $1$, unless the correct value can be inferred by an efficiently implementable rule (like small-width resolution; or being implied by a small set of clauses). We show that PPSZ performs exponentially better than previously known, for all $k \geq 3$. For Unique-$3$-SAT we bound its running time by $O(1.306973^{n})$, which is somewhat better than the algorithm of Hansen, Kaplan, Zamir, and Zwick, which runs in time $O(1.306995^n)$. Before that, the best known upper bound for Unique-$3$-SAT was $O(1.3070319^n)$. All improvements are achieved without changing the original PPSZ. The core idea is to pretend that PPSZ does not process the variables in uniformly random order, but according to a carefully designed distribution. We write "pretend" since this can be done without any actual change to the algorithm.
