Is the verifier for an $NP$ and its $co-NP$ the same?

Question

I have a hard time to find the goal of having $co-NP$ problems.

• $NP$: Is there a Hamiltonian path in this graph?

We need to bring a certificate, and the verifier checks the certificate in polynomial time. However, finding such a path might not be done in polynomial time. It may need searching the entire problem space.

• $co-NP:$ Isn't there any Hamiltonian path in this graph?

To say "no", we need to bring a counterexample, and the counterexample (the same certificate) is checked by [the same] verifier in polynomial time. However, finding such a counterexample might not be done in polynomial time. It may need searching the entire problem space.

Am I right in the definition of my examples?

It seems we can reduce them to each other:

For example, "Isn't there any Hamiltonian path in this graph?" We ask the complement $NP$ problem "Is there any Hamiltonian path in this graph", if it said "Yes", we would say "No" to the $co-NP$ problem and if it said "No", we would say "yes" to the $co-NP$ problem.

So, what is actually the difference? Is it just playing on words? Are there questions for which the NP and its co-NP different to answer?

Anyway, I don't know the goal here, please guide me.

Answer 1

I think you might be slightly confusing your definition for co$NP$. To show that a certain graph doesn't contain a Hamiltonian path, you need to show that all paths in it aren't Hamiltonian, and providing a specific path as a "counter example" isn't enough.

In general, $coNP$ isn't defined using a witness the same way $NP$ is, because if it did than it would be the same as $NP$, and for now this is an open problem (we don't know if the two are equal, and they are usually believed to be different). Therefore, it doesn't really make sense to talk about a witness for a $coNP$ problem the same way you talk about a witness for an $NP$ problem.

Specifically, for a certain language in $coNP$ and a witness-based TM $M$ accepting it, $x$ is in the language iff $M$ accepts $(x,v)$ for all witnesses $v$. This is in contrast to a TM for a language in $NP$ that needs to accept only for a single witness.

I would like to add that for me, studying about the Polynomial Hierarchy using its witness-related definitions helped me understand $coNP$ better, but it isn't a necessity.

Answer 2

Taking an $\mathtt{NP}$ problem, formulating its complement, and then looking at their verifiers is pointless, because of this logical equivalence:

$$\neg \exists x. P(x) \equiv \forall x. \neg P(x)$$

So, you are right that this is a boring thing to do.

However, consider a decision version of factorization problem:

Given integers $N$ and $B$, is there an integer $x$, such $1 < x < B$ and $x$ divides $N$?

"Yes" answer is certified by $x$ itself: just perform the division.

"No" answer is certified by the full factorization of $N$: we can check that each factor is prime and their product is $N$ (so this is indeed the factorization) and none of the factors satisfies $1 < x < B$.

The conclusion is that factorization is both $\mathtt{NP}$ and $\mathtt{coNP}$. It is considered highly unlikely that $\mathtt{NP} = \mathtt{coNP}$, so it follows that factorization hardly can be $\mathtt{NP}$-complete. And now this is something interesting to say.