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

> **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?  

---

