Jump to content

Talk:FP (complexity)

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Relevant discussion

[edit]

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

[edit]

Let denote triples where is a graph and and are vertices of . Let be the set of all pairs where is the length of a simple path from to in . Then is in as witnessed by any shortest path algorithm, but is not in unless the Longest Path problem is in , i.e., unless .--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?

[edit]

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]