I ask a question before, Questions on Graph and Hamiltonian, but i ask it here with different challenging contest.From this book and other study in complexity theory, I have seen the following statement:The definition of NP is not symmetric with respect to yes-instances and no-instances.  For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?However, I was wondering if this this problem was NP-Complete.  Could someone let me know if the following statement true?Determining a that a Graph is not Hamiltonian is in NP-Class.I read another book on this book on end of page 306, the authors wrote this is NP-Hard. anyone could clarify me?
Not Hamiltonian is in NP Class?
complexity theory;graph theory;np complete;np hard;decision problem
The statementDetermining a that a Graph is not Hamiltonian is in NP-Class.is neither true nor false. It doesn't have a truth value, since there's a type mismatch. Similarly, the statementThe color red is in NP.is neither true nor false.Here is something which is true. Let $L$ be the language of all Hamiltonian graphs. That is, $x \in L$ if $x$ encodes a Hamiltonian graph. (We fix the encoding once and for all.) The language $L$ is in NP since to prove that $x \in L$, one just needs to present a Hamiltonian circuit (a proof whose size is polynomial in the input size), and this proof can be verified in polynomial time.Furthermore, $L$ is NP-complete. The book you're consulting probably has a proof. Therefore, if $L$ were in coNP, then NP=coNP, which is believed to be false. So it is probably the case that $L$ is not in coNP. But we don't know for sure.The language $L'$ of non-Hamiltonian graphs is the complement of $L$ (modulo boring technicalities arising from the fact that not every string encodes a graph). Since $L$ is NP, $L'$ is in coNP. We can also see it directly: to prove that $x \notin L'$, one just needs to present a Hamiltonian circuit. Furthermore, $L'$ is coNP-complete, since $L$ is NP-complete. Again, it is probably the case that $L'$ is not in coNP, since otherwise NP=coNP, which is believed to be false.