Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR20-011 | 9th February 2020 18:50

Super Strong ETH is true for strong PPSZ

RSS-Feed




TR20-011
Authors: Dominik Scheder, Navid Talebanfard
Publication: 16th February 2020 08:21
Downloads: 783
Keywords: 


Abstract:

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).



ISSN 1433-8092 | Imprint