ECCC-Report TR20-011https://eccc.weizmann.ac.il/report/2020/011Comments and Revisions published for TR20-011en-usSun, 16 Feb 2020 08:21:24 +0200
Paper TR20-011
| Super Strong ETH is true for strong PPSZ |
Navid Talebanfard,
Dominik Scheder
https://eccc.weizmann.ac.il/report/2020/011We 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).Sun, 16 Feb 2020 08:21:24 +0200https://eccc.weizmann.ac.il/report/2020/011