Hamiltonian cycle vs co-NP [closed]

Question

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)?

Update

1. To put it simply, returning an opposite answer for one input does not cover for all possible inputs.

2. In the comments of dkaeae's answer below, I say "NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian." Fact is if a P-machine can decide whether a graph is Hamiltonian or not, it can also deliver an instance of such a cycle in P-time if any exist. This does not harm the formal definition of NP.

Answer 1

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.

Answer 2

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.

Answer 3

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.