2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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$ Commented 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$ Commented Nov 1, 2017 at 8:42

1 Answer 1

Reset to default
4
$\begingroup$

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$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ What do you do when you see both positive and negative answers? $\endgroup$ Commented 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$ Commented 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$ Commented 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$ Commented Nov 2, 2017 at 14:56
  • $\begingroup$ @chi.. Thanks. Can you please explain why $2poly(m')+1$ tests suffice? $\endgroup$ Commented Nov 2, 2017 at 16:33

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.