主观题：The longest Hamiltonian cycle

The longest Hamiltonian cycle problem is to find a simple cycle of maximum length in a graph.  To prove that it is NPC, we must first prove that it is in NP -- that is, to prove that an answer can be verified to be correct in polynomial time.

To verify that a cycle is Hamiltonian is easy. But how would you know if a cycle really is the longest?






答案：When we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the **decision version** of that problem.

Here, the decision version is:

Does the weighted graph G have a Hamiltonian path with total weight at least K?

For this problem, verification of the witness (=solution) is easy: we can easily check whether the solution path has weight at least K. So, the decision version is in NP.