The question is to show that there is no deterministic polynomial time algorithm that solves SAT correctly on all but $poly(m)$ formulas of size $m$, for every $m \geq 0$ unless $P \ne NP$.

I know that if $P = NP$, a polynomial time algorithm exists that, given a Boolean formula φ, actually produces a satisfying assignment for φ if it is satisfiable. But I can't really understand how a poly time algorithm can solve SAT correctly on only $poly(m)$ formulas, if $P \neq NP$. Am I missing something in understanding the problem or there is a catch?

  • $\begingroup$ It isn't very helpful to know an algorithm that solves only $poly(m)$ formulas -- for example, an algorithm that checks whether the input is one of 42 particular instances to which you know the correct answer, and reports that answer if so, is such an algorithm. Your goal here is instead to show that, if an algorithm that could solve all but $poly(m)$ instances in polynomial time actually existed, this would imply that $P = NP$. $\endgroup$ Nov 1, 2017 at 8:37
  • $\begingroup$ Hint: You can prove this by designing a poly-time algorithm that would solve every formula of size $m$; this poly-time algorithm is allowed to call the hypothetical "solves-all-but-$poly(m)$-instances" algorithm a polynomial number of times (as well as do at most a polynomial amount of other work). $\endgroup$ Nov 1, 2017 at 8:42

1 Answer 1


I'll provide a sketch.

Given any formula $\varphi$ of size $m$, we can rewrite it in an equisatisfiable way as $\varphi \land p$ where $p$ is a fresh propositional variable. In this way, we can generate an infinite amount of equisatisfiable formulas.

Now, exploiting this, it is easy to find a way to generate, in PTIME, $2 poly(m')+1$ formulas $\varphi'$ equisatisfiable wrt $\varphi$, where each such $\varphi'$ is of size $m'$. We can then decide SAT on $\varphi$ by taking what is the result of the majority of $\varphi'$ instances ($poly(m')+1$ instances), and return that. Indeed, among the $2poly(m')+1$ test, at most $poly(m')$ can have a wrong result, so the result of the majority must be the correct one.

This runs a PTIME algorithm a polynomial number of times ($2 poly(m')+1$, where $m'$ is polynomial wrt $m$), so we indeed solve SAT in PTIME.

To generate all the needed $\varphi'$, we note that the "longest" variable name in $\varphi$ can't more than $m$ bit long for obvious size reasons. Hence if we take $p$ to be any variable whose name has size $m+1$ bits it is surely fresh, and this makes $\varphi'$ to have size $m' = m+(m+1)+O(1)$. Further, we have $2^{m+1}$ choices of such $p$, which is (asymptotically) a large enough space to choose $2 poly(m')+1$.

  • $\begingroup$ What do you do when you see both positive and negative answers? $\endgroup$
    – Ariel
    Nov 1, 2017 at 9:53
  • 1
    $\begingroup$ @Ariel Thank you! I indeed missed that point. However, it is enough to test for $2 poly(m')+1$ instances: on these only $poly(m')$ can be wrong, hence the majority decides the outcome. So, at least there's a fix. $\endgroup$
    – chi
    Nov 1, 2017 at 13:34
  • $\begingroup$ @chi can you shed some light on how to rewrite any $\phi$ in an equi-satisfiable way as you have shown? Are you trying to convert it into CNF-form with exponential number of clauses? $\endgroup$
    – chelsea
    Nov 2, 2017 at 14:26
  • $\begingroup$ @chelsea I'm only appending $\land p$ to the original formula, leaving it as it is. No CNF involved, I'm just adding one clause at the end. I just choose $p$ to be an unused variable, in many (polynomally bounded) ways. $\endgroup$
    – chi
    Nov 2, 2017 at 14:56
  • $\begingroup$ @chi.. Thanks. Can you please explain why $2poly(m')+1$ tests suffice? $\endgroup$
    – chelsea
    Nov 2, 2017 at 16:33

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.