# FNP complexity class

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?

• 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. :-) – Aaron Sterling Sep 9 '10 at 17:16
• okay, then I'll ask this as a separate question and link to this question (waiting for moderators to respond) – dhruvbird Sep 9 '10 at 17:27
• 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. – Suresh Venkat Sep 9 '10 at 17:29
• 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. – Suresh Venkat Sep 9 '10 at 17:30

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".

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.

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)".