Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was

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?

share|cite|improve this question
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
up vote 8 down vote accepted

See the FAQ: 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".

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer
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? – Tayfun Pay Dec 9 '11 at 0:53

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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