Tong Qin, Osamu Watanabe

We propose a simple idea for improving the randomized algorithm of Hertli for the Unique 3SAT problem.

more >>>Dominik Scheder, Navid Talebanfard

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