0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you misunderstood the OP. He asked about verifiers for “no” instances, which are indeed the same as for NP “yes” counterparts. $\endgroup$ – Dmitri Urbanowicz Dec 3 '18 at 8:04
  • $\begingroup$ @DmitriUrbanowicz If that's the case than I did misunderstand the question. However, it does seem to me that OP is somewhat confused about the very definition of $coNP$, and in particular his use of the term "counter example" in the context of a $coNP$ language is misleading. $\endgroup$ – Dean Gurvitz Dec 3 '18 at 8:11
  • $\begingroup$ You mean finding a "yes" answer for a $coNP$ isn't straightforward and needs to check all possible paths. However, saying "no" to an $NP$ problem isn't straightforward too. "Is there a Hamiltonian path"? To say "no" you must check all paths and say none of them are Hamiltonian. I mean these two questions are the mirror of each othere, at least in this case. $\endgroup$ – Ahmad Dec 3 '18 at 8:13
  • $\begingroup$ @Ahmad You are right. Finding a no answer to an $NP$ problem isn't straightforward, and is equivalent to finding a yes answer to a $coNP$ problem. In both cases, a single witness wouldn't suffice, and one needs to show a certain property holds for all possible witnesses. $\endgroup$ – Dean Gurvitz Dec 3 '18 at 8:16
  • 1
    $\begingroup$ @Ahmad Exactly. That's why you can't define $coNP$ using a witness - because accepting a single witness wouldn't be enough for coNP. It needs to satisfy a property for all witnesses. That is actually the exact definition of $coNP$ in the Polynomial Hierarchy that I mentioned, in case you're interested. $\endgroup$ – Dean Gurvitz Dec 3 '18 at 8:23
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Isn't factorization $NP-Complete$? I've heard it is $NP-Hard$ and for this reason, cryptography methods are secure! am I mistaken? $\endgroup$ – Ahmad Dec 3 '18 at 11:12
  • $\begingroup$ You are mistaken. Factorization is not known to be NP-hard. $\endgroup$ – Dmitri Urbanowicz Dec 3 '18 at 11:15
  • $\begingroup$ Check this. It says there is no proof of either case. $\endgroup$ – Ahmad Dec 3 '18 at 11:22
  • $\begingroup$ Haven’t I said the same? $\endgroup$ – Dmitri Urbanowicz Dec 3 '18 at 12:59
  • $\begingroup$ Right so it's currently neither P nor NP-Complete. I thought every NP that is not P is NPC. But it seems like that I mistook $\endgroup$ – Ahmad Dec 3 '18 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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