This post is linked to: FNP complexity class
Many places say that the decision version of Hamiltonian Cycle is NP-Complete, and NP-Complete problems are those whose solution can be verified in polynomial time.
Suppose I ask someone "Does a Hamiltonian Cycle exist?" and she answers "YES", then how can I (in polynomial time) verify that she is not lying? (I am assuming here that the solution I got "YES" is the only thing I have with me)
Alternate interpretation: Is "Any given solution to L can be verified quickly (in polynomial time)" to be interpreted as "Given some solution to the Hamiltonian Cycle problem for this graph, it can be verified quickly"?
If it is the latter, then things fall into place.
Quoting from http://en.wikipedia.org/wiki/FNP_(complexity): "This means that the FNP version of every NP-complete problem is NP-hard."
Is this necessarily true?
And comparing with the Hamiltonian Cycle problem, if she (the solver) says "YES and here it is ..." then I can take that and verify if it is actually a Hamiltonian Cycle. Hence, shouldn't this (FNP) version
actually be NP-Complete not be NP-hard? What am I missing here?