Hamiltonian cycle vs co-NP I am trying to understand co-NP and its implications properly.
The French Wikipedia page describing co-NP provides the &quot;complementary&quot; 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

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

In the comments of dkaeae's answer below, I say &quot;NP is not only about checking if a cycle is Hamiltonian. It is about finding any that would be Hamiltonian.&quot; 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.
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.