Talk:FP (complexity)

Relevant discussion

This meaning of FP does not appear universal, some restrict it to function problem, not to search problems as defined here, but incorrectly stated as being about function problems. Further discussion at Talk:function problem. Please reply there to keep the discussion centralized. Pcap ping 00:36, 9 September 2009 (UTC)

Why is FP $\subseteq$ FNP?

Let $x$ denote triples $(G,s,t)$ where $G$ is a graph and $s$ and $t$ are vertices of $G$. Let $R$ be the set of all pairs $(x,y)$ where $y$ is the length of a simple path from $s$ to $t$ in $G$. Then $R$ is in $FP$ as witnessed by any shortest path algorithm, but $R$ is not in $FNP$ unless the Longest Path problem is in $P$, i.e., unless $P=NP$.--GPhilip (talk) 09:52, 27 September 2009 (UTC)

FP is in FNP for the same reason that P is in NP. A deterministic machine is a special case of a non-deterministic machine. --Robin (talk) 19:42, 22 November 2009 (UTC)

How can "FP = FNP" hold?

Since FNP contains relations for which there exists x with no y such that P(x,y) holds, how can "FP = FNP" hold? 132.65.120.151 (talk) 14:13, 13 December 2015 (UTC)