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.