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.

  • $\begingroup$ Well, how did you infer it, and what part of the inference in specific are you unsure about? $\endgroup$ – Tom van der Zanden Feb 17 '15 at 19:45
  • $\begingroup$ 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? $\endgroup$ – M. holi Feb 17 '15 at 19:48
  • $\begingroup$ @M.holi When someone says something is an "open" problem, that means that no one knows the answer yet. $\endgroup$ – apnorton Feb 18 '15 at 0:33
  • $\begingroup$ Dear @anorton, can we say No-Hamiltonian is in NP Class? $\endgroup$ – M. holi Feb 18 '15 at 6:35

No, determining whether a graph is not Hamiltonian is coNP-complete, and it is believed not to be NP-complete, indeed not in NP. Determining what a graph is Hamiltonian is NP-complete.

| cite | improve this answer | |
  • $\begingroup$ would you please interpret this sentence : "Note that if such a method were known, then we would know that the hamiltonian cycle problem was in co-NP. Since it is already known to be NP-complete, this would imply that NP=co-NP", infact i means ""Since it is already known to be NP-complete"" what does mean? now np-complete or co-NP? $\endgroup$ – M. holi Feb 17 '15 at 20:00
  • $\begingroup$ Sounds like you're having English issues. "Since it is already known to be NP-complete" states that the problem [being Hamiltonian] is NP-complete; and that this fact implies [the rest of the sentence]. So "it" refers to the Hamiltonian cycle problem, rather than to co-NP. $\endgroup$ – Yuval Filmus Feb 17 '15 at 21:00
  • $\begingroup$ I'm Sorry Filmus, so my final question is Not Hamitonian is co-NP-Complete, can we say it is in NP Class? $\endgroup$ – M. holi Feb 18 '15 at 6:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Yuval Filmus Feb 18 '15 at 15:36
  • 1
    $\begingroup$ I think it's better if you answered this question yourself. Make sure you understand the argument for Hamiltonian. You should be able to reproduce it and come to the correct conclusions for not Hamiltonian on your own. $\endgroup$ – Yuval Filmus Feb 18 '15 at 15:43

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