New answers tagged

1 vote
Accepted

Calculation on Sparsification and critical clauses in SAT

First part: $2^{h(\delta)n}+2^{\epsilon n}+2^{\epsilon n}2^{(s_k+ \epsilon)(1-(\delta/ek))n} \leq 2^{(s_\infty(1-d/k)+2\epsilon)n}$ $\implies2^{(s_\infty/2)n} + 2^{(s_k+ \epsilon)(1-(\delta/ek))n +\...
5 votes
Accepted

Time complexity of PPZ algorithm

$\let\ep\varepsilon$Note that the stated estimate $\tilde O\bigl(2^{H(\ep)n}\bigr)$ on the volume of the Hamming ball only holds for $\ep\le1/2$ (for $\ep\ge1/2$, it stays $\Theta(2^n)$). As the paper ...
Emil Jeřábek's user avatar

Top 50 recent answers are included