# Questions on Graph and Hamiltonian [closed]

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 an NP-Complete problem.

• Well, how did you infer it, and what part of the inference in specific are you unsure about? – Tom van der Zanden Feb 17 '15 at 19:45
• Dear @TomvanderZanden, i'm not sure, if a question is open (specially not a hamilton graph), can we say NP or NP-complete or ? and then would you please correct me? – M. holi Feb 17 '15 at 19:48
• @M.holi When someone says something is an "open" problem, that means that no one knows the answer yet. – apnorton Feb 18 '15 at 0:33
• Dear @anorton, can we say No-Hamiltonian is in NP Class? – M. holi Feb 18 '15 at 6:35

• @M.holi I suggest you go over your basics. Make sure that you understand what NP and coNP are, and what NP-hard and coNP-hard mean. NP and coNP are not the same. The language $L$ consisting of all Hamiltonian graphs is NP but probably not coNP – we don't know for sure, but since we believe that NP≠coNP, and $L$ is NP-complete, then it must be the case that $L$ is not in coNP. – Yuval Filmus Feb 18 '15 at 15:36