Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR20-011 | 9th February 2020 18:50

#### Super Strong ETH is true for strong PPSZ

TR20-011
Authors: Dominik Scheder, Navid Talebanfard
Publication: 16th February 2020 08:21
We construct $k$-CNFs with $m$ variables on which the strong version of PPSZ $k$-SAT algorithm, which uses bounded width resolution, has success probability at most $2^{-(1 - (1 + \epsilon)2/k)m}$ for every $\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches through small subformulas of the CNF to see if any of them forces the value of a given variable, and for strong PPSZ the best known previous upper bound was $2^{-(1 - O(\log(k)/k))m}$ (Pudlák et al., ICALP 2017).