Talk:FP (complexity)

Mathematics Stub‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

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)[reply]

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)[reply]

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)[reply]

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)[reply]

Relevant discussion

Why is FP ⊆ {\displaystyle \subseteq } FNP?

How can "FP = FNP" hold?

Why is FP $\subseteq$ FNP?