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?

Improve this question
$\endgroup$
4
  • 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, 2010 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, 2010 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, 2010 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, 2010 at 17:30

3 Answers 3

Reset to default
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".

Improve this answer
$\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.

Improve this answer
$\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)".

Improve this answer
$\endgroup$
1
  • $\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, 2011 at 0:53

Your Answer

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

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