7
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ I think your question is very vague. It is as if you are saying that FNP is the class of NP-complete problems, which is plain wrong. Please restate your question in a better way. $\endgroup$
    – Sadeq Dousti
    Commented Sep 9, 2010 at 18:16
  • $\begingroup$ I am actually trying to figure out why the FNP version of the decision version of the Hamiltonian Cycle problem should be termed as NP-hard. $\endgroup$
    – dhruvbird
    Commented Sep 9, 2010 at 18:20
  • $\begingroup$ All NP-complete problems are also NP-hard. (NP-completeness means being NP-hard and being a member of NP.) The search version, essentially by default, solves the decision version. Hence, if the decision version is NP-hard, then the search version must be NP-hard too (else, it would contradict the decision version's NP-hardness). $\endgroup$
    – Daniel Apon
    Commented Sep 9, 2010 at 22:46

2 Answers 2

Reset to default
7
$\begingroup$

The FNP version of an NP-complete language $L$ asks to solve the following problem on every input $x$:

1) If $x \not\in L$, output "NO".

2) If $x \in L$, output some witness "w" such that a polynomial-time entity, given $(x,w)$, can verify that $x \in L$.

Consider the transformation $T$ of the above scheme: If the FNP machine answered "NO", $T$ answers "NO". Otherwise, $T$ answers "YES".

Obviously $T$ is a Karp-reduction of any NP-complete problem to the corresponding FNP-complete instance.

Improve this answer
$\endgroup$
1
  • $\begingroup$ okay I think I have finally understood it. Just to re-iterate: Since every decision problem can be reduced to its corresponding FNP version, it is no harder than it. However, I was wondering if both need the same method to solve. i.e. Is the decision problem any easier than the FNP one which asks for the answer. I think this "A basic question about FNP problems is whether they're self-reducible; that is, whether they reduce to the corresponding NP decision problems" from the complexity Zoo link clarifies it. Thanks!! $\endgroup$
    – dhruvbird
    Commented Sep 10, 2010 at 5:55
2
$\begingroup$

FNP-Complete problem is the search version of an NP-complete decision problem "Is there a Hamiltonian graph in the input graph". The search version which is FNP-complete asks for an algorithm that produces the edges of a Hamiltonian cycle or report there is none. As far as verifying the correctness of the decision problem, you can use it as oracle to find the Hamiltonian cycle and then verify that the cycle is Hamiltonian.

Improve this answer
$\endgroup$
2
  • $\begingroup$ okay so I am guessing that my original dilemma about trying to classify the FNP version as NP-complete was incorrect since the FNP version of the decision problem involves generating the solution. However since I can always verify the solution in polynomial time, would it be right to say that the FNP version is NP-hard? $\endgroup$
    – dhruvbird
    Commented Sep 9, 2010 at 18:06
  • 1
    $\begingroup$ problems in FNP are "search problems", and problems from NP are "decision problems". The definitions of FNP and NP are different and it is not correct to say that a problem in TFNP is hard for NP or viceversa. Indeed, $NP\neq P$ iff $FNP \neq FP$, because search problem and their corresponding decision versions are polynomially related. $\endgroup$
    – Marcos Villagra
    Commented Sep 9, 2010 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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