Suppose you have an NP problem, and a polynomial time verifier which accepts valid solutions within $f(n)$ operations.

You make a tweak to the verifier program, so that if it takes more than $f(n)$ operations, it unconditionally rejects. Then you place it into an NP machine and run it on all possible certificates for some instance of the problem where you're not sure if it has a solution. The unconditional reject after $f(n)$ operations ensures the computation terminates within $f(n)$ operations, even when rejecting. So this NP machine can solve the co-NP dual of the NP problem, where you want to reject in polynomial time when there is no solution.

Except that can't be right, because it seems to imply $\mathsf{NP}=\mathsf{coNP}$ and that's not believed to be true. I have an incorrect assumption or inference somewhere. What is it? Why can't I avoid NP's "negatives might run for a long time or even forever" with algorithm-specific time cutoffs?

A concrete example: suppose you have a 3-SAT verifier that takes no more than $42 n^2$ operations to check a solution to an $n$-clause problem (involving up to $3n$ variables). You then make an NP program like "non-deterministically choose a variable assignment, run verifier for up to $42 n^2$ steps, return its result else reject if it didn't finish". So within $42 n^2$ operations we'll have an answer, and flipping it gives the "is there no satisfying assignment" answer. Why is this not an NP algorithm for the co-NP problem of determining if there is no satisfying assignment to a 3-SAT problem?


The mistake I made was in the very last step: flipping the result. Doing that requires more than an $\mathsf{NP}$ machine, because I'm recombining the massively parallel computation then doing something else. $\mathsf{NP}$ machines finish with the merging, they can't continue on.

To run my algorithm I'd need a machine with the ability to query an $\mathsf{NP}$ machine then continue. A $\mathsf{P^{NP}}$ machine can do that... but it makes sense that $\mathsf{P^{NP}}$ would contain $\mathsf{coNP}$.

See also: Oracle Machines (Complexity Classes), and the Polynomial Hierarchy.

| cite | improve this answer | |
  • $\begingroup$ Yes, good summary of the issue. $\endgroup$ – usul Mar 3 '14 at 2:26

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