The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a randomized algorithm for finding a satisfying assignment for such $\varphi$.

So basically I've read about the $WALKSAT$ algoritm which starts with some random assignment, $\alpha_1$ and for every iteration chooses randomly an unsatisfied clause, $l$ of $\varphi(\alpha)$ and a literal of $l$. Then, it flips this literal in $\alpha_1$, getting a new assignment, $\alpha_2$.

We repeat this process within a time bound $t$ or until a satisfying assignment has been found.

I've understood that this algorithm could be suitable here. I need to show that there's a probability of $\frac{1}{2}$ finding a satisfying assignment (probably after amplification)

I think we should look at the hamming distance of $\alpha, \alpha^t$ where $\alpha$ is the assignment as described in the question and $\alpha^t$ is unsatisfying assignment after $t$ iterations.

I'd be glad if you could guide from this point.



1 Answer 1


The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-clause, then flipping a random variable decreases the distance between $\beta$ and $\alpha$ with probability at least $1/k$. In your case, you can get a better guarantee since $\alpha$ satisfies half the literals in every clause.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.