Loading jsMath...
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: 925
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