From this book and other study in complexity theory, I have seen the following s
ID: 649281 • Letter: F
Question
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.
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.