4
$\begingroup$

Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was http://en.wikipedia.org/wiki/FNP_(complexity)

However, that isn't sufficient for me to understand what that class actually means. For example, what should the FNP version of the decision version of the Hamiltonian Cycle Problem be?

$\endgroup$
  • 2
    $\begingroup$ From the FAQ: "This is not a discussion board, this is a place for questions that can be answered!" My reading of that is that it would be better if you asked a specific question, got specific answers, and then asked a new question, instead of using a single question as a forum. If a mod posts to correct me, then I'm wrong. :-) $\endgroup$ – Aaron Sterling Sep 9 '10 at 17:16
  • $\begingroup$ okay, then I'll ask this as a separate question and link to this question (waiting for moderators to respond) $\endgroup$ – dhruvbird Sep 9 '10 at 17:27
  • $\begingroup$ I agree with Aaron. This is a preferred strategy. It also causes less confusion, because otherwise answers given for the unedited question will make no sense after the edit. $\endgroup$ – Suresh Venkat Sep 9 '10 at 17:29
  • $\begingroup$ p.s you don't have to wait for mods :). post a question on meta and/or wait for community feedback. the mods merely have power to enforce what the community thinks. we don't make policy. $\endgroup$ – Suresh Venkat Sep 9 '10 at 17:30
9
$\begingroup$

See the FAQ: Official FAQ for Theoretical Computer Science for more info on complexity classes. Papadimitriou's complexity textbook also has a nice explanation of FNP.

As for your specific question, the FNP version is merely, "given a graph G, determine if a Ham cycle exists and find it".

$\endgroup$
9
$\begingroup$

The Hamiltonian Cycle Problem asks to decide, given a graph $G$, whether $G$ is Hamiltonian. This is the decision version. The function version(FNP) asks to actually find a Hamiltonian cycle in $G$ (if any).

I suggest looking at FNP, and related classes (such as NPMV and NPSV) in the Complexity Zoo.

In addition, a quick search in Google Books reveals many books in which you may find more info.

Please be more specific if you have more questions in mind.

$\endgroup$
6
$\begingroup$

As an interesting aside, an exactly equivalent class $PC$, short for "Polynomial-time Check," shows up in Goldreich's complexity textbook. $FNP$ is still correct for this site as we've elected to follow the naming conventions of the Complexity Zoo (referenced in Suresh's answer, and in the FAQ).

The completely informal way to define $FNP$ is simply "the class of search analogues of NP problems." As others have mentioned, the $NP$-version of HAMILTONIAN CYCLE is "Does the given graph have a Hamiltonian cycle? (Yes or No)" whereas the $FNP$-version of HAMILTONIAN CYCLE is "In the given graph, what is the Hamiltonian cycle? (Either output such a cycle, or output None exists)".

$\endgroup$
  • $\begingroup$ So the FNP-version of SAT is "In the given Boolean formula in CNF, what is the assignments to the variables that satisfy it?" Is that it? $\endgroup$ – Tayfun Pay Dec 9 '11 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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