This is third-hand, so please bear with me. A collaborator was at a review meeting where he heard another participant make the claim that given an assignment for a SAT problem that satisfies (some high percentage) of clauses, there are polynomial time algorithms that finish the problem.

Is this true? Can someone point me to some references?

  • $\begingroup$ Academic telephone is a terrible game. The original comment was a reference to PCP theorems... $\endgroup$ – Andrew Mar 2 '17 at 2:13

This cannot be true, since you could use such an algorithm to solve SAT itself in polynomial time. Given a SAT instance $\varphi$, construct a much larger instance $\psi$ which contains $\varphi$ as well as many copies of the clause $x$, where $x$ is a new variable not appearing in $\varphi$. It is easy to find an assignment satisfying almost all clauses of $\psi$. Now run your algorithm. If it succeeds, then $\varphi$ is satisfiable; and moreover, if $\varphi$ is satisfiable then it should, indeed, succeed. Thus $\varphi$ is satisfiable iff your algorithm finds a satisfying assignment within the promised running time.

Perhaps the participant meant an assignment which is close to a satisfying assignment, as in Schöning's kSAT algorithm; see for example Eppstein's lecture notes.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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