6
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ This question is indeed related. $\endgroup$
    – Raphael
    Commented Mar 3, 2014 at 7:03

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Yes, good summary of the issue. $\endgroup$
    – usul
    Commented Mar 3, 2014 at 2:26

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