0
$\begingroup$

I am trying to understand co-NP and its implications properly.

The French Wikipedia page describing co-NP provides the "complementary" version of the Hamiltonian cycle in co-NP as follows:

Considering a graph G, is it true that it does not have an Hamiltonian cycle?

Is this correct?

If so, then how is this complementary version a different class of complexity than the original Hamiltonian cycle problem? The decision question is the same. To put it differently, what is the difference between NP and co-NP here?

Otherwise, if this complementary version is false, what would be the correct version (if any exists)?

$\endgroup$

closed as off-topic by Gamow, Emil Jeřábek supports Monica, domotorp, Marzio De Biasi, Hsien-Chih Chang 張顯之 Jan 4 at 23:16

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Gamow, Emil Jeřábek supports Monica, domotorp, Marzio De Biasi, Hsien-Chih Chang 張顯之
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

The complementary version given by Wikipedia is correct.

coNP consists of the complements of the problems in NP. In this case, the universe of discourse (i.e., the encoded instances) is the set of (properly encoded) graphs. The Hamiltonian cycle decision problem contains those graphs which are Hamiltonian; its complement is exactly the set of graphs which are not Hamiltonian.

You are correct; the two problems do look almost the same. This is a vital realization concerning coNP (or any co-class in fact). The key difference is that, for some problem classes, being able to efficiently check whether a solution is correct (NP) does not necessarily mean you can also efficiently verify all answers are incorrect (coNP) and vice-versa.

$\endgroup$
  • $\begingroup$ So, it seems to me that the Hamiltonian cycle is both in NP and co-NP. Otherwise, what am I missing? $\endgroup$ – Jérôme Verstrynge Dec 31 '18 at 23:24
  • 1
    $\begingroup$ @Jérôme Verstrynge Given a graph and a cycle, you can easily check if it is a Hamiltonian cycle (NP). Can you also easily check if all cycles are not Hamiltonian (i.e., no cycle is Hamiltonian; coNP)? I think not. $\endgroup$ – dkaeae Dec 31 '18 at 23:53
  • $\begingroup$ Well, NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian. If you find any, then you also solve the "complementary" version of the problem immediately and if you can't find any, then it means you have exhausted (or eliminated) all possibilities, which is, by definition the "complementary" problem itself. This is why I think NP = co-NP here. Anyway, thanks, you have clarified the concept for me. That was my question. $\endgroup$ – Jérôme Verstrynge Jan 1 at 8:44
  • 2
    $\begingroup$ @Jérôme Verstrynge This is hardly a matter of "opinion" since there is no dissension concerning the definition of NP (at least not in the proper circles of science). NP contains decision problems. Period. $\endgroup$ – dkaeae Jan 1 at 18:05
  • 2
    $\begingroup$ Finding an HC is often described as a NP problem in many books and articles. This is plainly not true.I do not know which books you are reading, but go on and read a proper complexity book like Papadimitriou, Arora&Barak, Goldreich. (e.g.: theory.cs.princeton.edu/complexity/book.pdf Section 2.6.1) $\endgroup$ – PsySp Jan 2 at 0:32
1
$\begingroup$

It might help to consider a different example. Given a number $n$, how would one succinctly prove that it is composite? Well, you can just provide a nontrivial factor. So COMPOSITES is obviously in NP. But given a number $n'$, how would you prove its not composite (i.e. prime)? That seems a lot harder. You can't just give a non-factor, you want to prove that there are no possible factors among the horde of numbers between 2 and $n'-1$ (which is exponential in the bit complexity of $n$). The space of possible factors is just too big for a proof by exhaustion.

Thus, while COMPOSITES is trivially in NP (problems whose yes instances have simple witnesses), it is a priori far from obvious whether or not it is also in coNP (problems whose no instances have simple witnesses).

Now let's get back to Hamiltonian cycles. if a graph has a Hamiltonian cycle, it's easy to give a witness that the cycle exists: just provide a description of the cycle itself. Thus, Hamiltonian Cycle is in NP. But if a graph does not contain a Hamiltonian cycle, and you want to prove that to someone, there is no good way, as far as anyone knows, to do so.

$\endgroup$
  • $\begingroup$ The counting problem is probably just as hard as the existential problem. NP is the problem class for finding single verifiable solutions. #P is the related problem class of counting solutions. Typically, sat and #sat are class representatives. 1.Valid programs for NP imply all solutions are acceptable as answers. 2.NP not equals #P implies not all solutions are answers. 3.Therefore, Validity implies NP equals #P. Line 1 expresses program validity and complete correctness. Line 2 interprets the inequality. Line 3 reasons about the first two lines. $\endgroup$ – daniel pehoushek Jan 2 at 15:14
  • 1
    $\begingroup$ I... um... what? No. $\endgroup$ – Yonatan N Jan 2 at 21:59
  • $\begingroup$ I admit its looks like a trivially short proof that NP=#P. But, thats after two decades of work on a #sat solver. Seriously, read slowly... I got banned for posting about it, so I desperately add comments where I may. GREs 2380/2400. $\endgroup$ – daniel pehoushek Jan 3 at 21:41
1
$\begingroup$

Jérôme, it seems to me that your initial confusion may be due to (unfamiliarity with) the different notions of Turing reduction and Karp reduction (at least, this was the case for me when I incurred into that very same confusion years ago; judging from your question and comments I can perceive my own flawed objections I had at that time).

What you (seem to) suggest in your comment, i.e. to invoke a solver for the $\mathbf{NP}$ problem and to invert its answer in order to solve the corresponding $\mathbf{coNP}$ problem, is a Turing reduction from Non-Hamiltonian Graph to Hamiltonian Graph: in order to solve the former problem we just give the same input graph to a subroutine which is able to solve the latter problem, and return YES if and only if the subroutine returned NO. Doing so does not remotely constitute a proof that Non-Hamiltonian Graph and Hamiltonian Graph have the same complexity, nor that $\mathbf{coNP} \subseteq \mathbf{NP}$, it is just an instantiation of the fact that $\mathbf{coNP} \subseteq \mathbf{P^{NP}}$, i.e. that you can efficiently solve any $\mathbf{coNP}$ problem using an oracle for any $\mathbf{NP}$-complete problem.

Now try to do the same using a Karp reduction instead of a Turing reduction. This is going to be much more uncomfortable: you cannot invert the answer of the subroutine, nor you can perform any manipulation of such answer, you can only return it as it is. The mind-boggling difficulty of proving (or disproving) $\mathbf{NP} = \mathbf{coNP}$ precisely resides here.

Of course you cannot give the same input graph to the subroutine, as the returned answer would be flat wrong. You have to smartly manipulate the input graph, modifying it in some clever way, and then feed the subroutine with such modified graph, so that the subroutine (which in your suggestion is a solver for Hamiltonian Graph, but in principle can be a solver for any $\mathbf{NP}$-complete problem) returns YES if and only if the original input graph is Non-Hamiltonian. See how dramatically clever such manipulation would have to be: it would mean that any Non-Hamiltonian graph given in input is transformed into a Hamiltonian graph (more generally into a YES instance of any $\mathbf{NP}$-complete problem, e.g. into a satisfiable CNF formula), and vice-versa! Proving $\mathbf{NP} = \mathbf{coNP}$ is equivalent to furnish such a fantastic mapping, disproving it is equivalent to proving that no such mapping can exist.

$\endgroup$
  • $\begingroup$ Thanks, indeed I was not aware of the difference between Turing and Karp reductions. Now I understand my flaw. $\endgroup$ – Jérôme Verstrynge Jan 3 at 13:31
  • $\begingroup$ You are welcome. $\endgroup$ – Giorgio Camerani Jan 3 at 15:01

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