# Algorithms for “mostly-SAT?”

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?

• Academic telephone is a terrible game. The original comment was a reference to PCP theorems... – 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.