Dominik Scheder - PPSZ is better than you think

theoretics:9832 - TheoretiCS, March 13, 2024, Volume 3 - https://doi.org/10.46298/theoretics.24.5
PPSZ is better than you thinkArticle

Authors: Dominik Scheder

    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.


    Volume: Volume 3
    Published on: March 13, 2024
    Accepted on: February 4, 2024
    Submitted on: July 25, 2022
    Keywords: Computer Science - Data Structures and Algorithms,68W20,F.2.2

    Consultation statistics

    This page has been seen 237 times.
    This article's PDF has been downloaded 232 times.