<p>The <strong>Hamiltonian Cycle Problem</strong> 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).</p>

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

<p>In addition, a quick search in <a href="http://www.google.com/search?tbs=bks:1&amp;tbo=1&amp;q=FNP+complexity&amp;btnG=Search+Books#hl=en&amp;tbo=1&amp;tbs=bks%3A1&amp;q=FNP+complexity+-proceedings+-annual&amp;aq=f&amp;aqi=&amp;aql=&amp;oq=&amp;gs_rfai=&amp;pbx=1&amp;fp=1c1bd44a83c0839f" rel="noreferrer">Google Books</a> reveals many books in which you may find more info.</p>

<p>Please be more specific if you have more questions in mind.</p>

CC BY-SA 2.5
2010-09-08T16:18:11.670Z
2010-09-08T16:18:11.670Z
Sadeq Dousti
<p>As an interesting aside, an exactly equivalent class $PC$, short for "Polynomial-time Check," shows up in <a href="http://www.wisdom.weizmann.ac.il/~oded/cc-book.html" rel="noreferrer">Goldreich's complexity textbook</a>. $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).</p>

<p>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 <em>None exists</em>)".</p>

CC BY-SA 3.0
2011-12-09T00:53:27.813Z
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
CC BY-SA 2.5
2010-09-08T17:35:46.707Z
2010-09-08T17:35:46.707Z
Daniel Apon
<p>See the FAQ: <a href="https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/229#229">Official FAQ for Theoretical Computer Science</a> for more info on complexity classes. <a href="http://books.google.com/books?ei=T7eHTM_cBYm6sAPvnOGvCg&amp;ct=result&amp;id=JogZAQAAIAAJ&amp;dq=papadimitriou+complexity&amp;q=FNP#search_anchor" rel="nofollow noreferrer">Papadimitriou's complexity textbook</a> also has a nice explanation of FNP. </p>

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

CC BY-SA 2.5
2010-09-08T16:19:21.777Z
2010-09-08T16:19:21.777Z
2017-03-16T15:45:13.547Z
Suresh Venkat
<p>Where can I find more information about the FNP complexity class? The only place I did find anything on FNP was <a href="http://en.wikipedia.org/wiki/FNP_(complexity" rel="noreferrer">http://en.wikipedia.org/wiki/FNP_(complexity</a>)</p>

<p>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 <em>Hamiltonian Cycle Problem</em> be?</p>

CC BY-SA 2.5
2010-09-09T17:16:03.630Z
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
CC BY-SA 2.5
2010-09-09T17:27:59.120Z
okay, then I'll ask this as a separate question and link to this question (waiting for moderators to respond)
dhruvbird
CC BY-SA 2.5
2010-09-09T17:29:25.750Z
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
CC BY-SA 2.5
2010-09-09T17:30:12.317Z
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
<cc.complexity-theory><complexity-classes><hamiltonian-paths>
FNP complexity class
dhruvbird
# FNP complexity class

(Asked by: username_0 on 2010-09-08)

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?

**Tags:** cc.complexity-theory, complexity-classes, hamiltonian-paths

> **Comments:**
> **username_1**: 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. :-)  
> **username_0**: okay, then I'll ask this as a separate question and link to this question (waiting for moderators to respond)  
> **username_2**: I agree with username_1. 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.  
> **username_2**: 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.  

---

## 3 answers

### Answer by username_2 on 2010-09-08. Score: 9 | Accepted answer

See the FAQ: [Official FAQ for Theoretical Computer Science](https://cstheory.meta.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/229#229) for more info on complexity classes. [Papadimitriou's complexity textbook](http://books.google.com/books?ei=T7eHTM_cBYm6sAPvnOGvCg&ct=result&id=JogZAQAAIAAJ&dq=papadimitriou+complexity&q=FNP#search_anchor) 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".


---

### Answer by username_3 on 2010-09-08. Score: 10

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](http://www.google.com/search?tbs=bks:1&tbo=1&q=FNP+complexity&btnG=Search+Books#hl=en&tbo=1&tbs=bks%3A1&q=FNP+complexity+-proceedings+-annual&aq=f&aqi=&aql=&oq=&gs_rfai=&pbx=1&fp=1c1bd44a83c0839f) reveals many books in which you may find more info.

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


---

### Answer by username_4 on 2010-09-08. Score: 7

As an interesting aside, an exactly equivalent class $PC$, short for "Polynomial-time Check," shows up in [Goldreich's complexity textbook](http://www.wisdom.weizmann.ac.il/~oded/cc-book.html). $FNP$ is still correct for this site as we've elected to follow the naming conventions of the Complexity Zoo (referenced in username_2'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*)".

> **Comments:**
> **username_5**: 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?  

---

