Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

This question already has an answer here:

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?

share|improve this question

marked as duplicate by D.W., David Richerby, FrankW, Ran G., vonbrand Jun 15 at 3:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1  
This question is indeed related. –  Raphael Mar 3 at 7:03

1 Answer 1

up vote 9 down vote accepted

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.

share|improve this answer
    
Yes, good summary of the issue. –  usul Mar 3 at 2:26

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