Talk:Function problem

I suggest this page be conjoined with and redirected to computation problem.Nortexoid 02:14, 23 Nov 2004 (UTC)

This article seems to spend more time talking about TSP then about function problems in general.

A possible error

It says: "For all function problems there is an analogous decision problem such that the function problem can be solved by polynomial-time Turing reduction to that decision problem."

It is true if the corresponding decision problem is NP-complete, but is it true in general? See, for example, Bellare & Goldwasser: The Complexity of Decision versus Search (can be found from Google Scholar).

For example, the decision problem of whether a game has a Nash equilibrium is trivial (the answer is always yes), but finding a Nash equilibrium (the corresponding function problem) was recently proved to be a difficult problem. —The preceding unsigned comment was added by 128.214.205.53 (talk) 13:03, 13 April 2007 (UTC).

It is, but the "analogous decision problem" isn't necessarily "determine if a solution exists". Generally it will be "determine if a solution exists satisfying certain constraints"; then you can find the solution with some sort of binary search. (In the TSP case, for example, the constraint is "total weight less than N"; without this constraint there would always be an optimal solution, since there are only finitely many possible solutions). Also, the solution function needs to be polynomially bounded, or it is obviously impossible to compute it in polynomial time, with any oracle. Ben Standeven 21:06, 25 April 2007 (UTC)

Terminology?

This article makes sense, but this is the first time I've encountered the terminology "function problem". Although not stated, presumably it is more general notion than optimization problem. Google books failed to find an adequate ref for this terminology [1]... Pcap ping 15:40, 7 September 2009 (UTC)

I thought the term was quite widely used to indicate the counterpart to decision problems where the answer is a number instead of 0 or 1. For instance, see Complexity Zoo's entry on FNP. --Robin (talk) 22:15, 7 September 2009 (UTC)

Not that widely used in books. Only a 2008 book has FP and FNP [2], but doesn't define "function problem". "Function problem" also doesn't apper in that many papers [3]. And I can't quite find a definition of "function problem" outside of FP and FNP, but presumably this isn't too much WP:OR. Pcap ping 22:53, 7 September 2009 (UTC)

For instance, Arora and Barak, Cambridge University Press, 2009, ISBN 978-0-521-42426-4 make no reference to "function problem", or even FP and FNP. Pcap ping 10:44, 8 September 2009 (UTC)

You're right. There's doesn't seem to be much mention of the term in books. Strange. --Robin (talk) 14:11, 8 September 2009 (UTC)

My vague recollection is that guys editing the complexity zoo wiki edited here too. Also, the zoo wiki has way more material than any complexity theory book. It's a bit silly to define FP and FNP without saying what F stands for as Elaine Rich does... I'd leave the after the "function problem" term in hope some finds a ref, or takes clue and writes it in a book :-) Pcap ping 14:26, 8 September 2009 (UTC)

There are several reasonable references in the first couple pages of this search: [4]. — Carl (CBM · talk) 21:25, 8 September 2009 (UTC)

Well, I've added one of those refs, but the article is not a bit contradictory because FP is defined for relations, not functions, that is, there may be more than one answer. But the ref I found requires that only one answer exist for a function problem. Bummer. Pcap ping 23:22, 8 September 2009 (UTC)

When more than one solution may exist, i.e. binary relation rather than function relates inputs and outputs, the problem is called a search problem by Greenlaw and Hoover, p. 51. Also, our article on FNP (complexity) cites a paper on search problems for a good reason! It should come as no surprize that "FP" and "FNP" are not that widely used since they are misnormers; the paper cited on FNP doesn't even use "FNP". Pcap ping 00:16, 9 September 2009 (UTC)

I'm not going to update the article unless someone agrees with me that FP and FNP are over search problems. I don't want to fix this article(s) just to be reverted... Pcap ping 00:21, 9 September 2009 (UTC)

The problem is actually more widespread. FP is defined by some authors as being about functions not relations as our article makes it to be. See for instance the 2nd and 3rd books here. I'm not sure how to reconcile all of these issues... Pcap ping 00:39, 9 September 2009 (UTC)

I always thought that FP was (as stated in the second reference you linked to) "the set of all functions from {0, 1}* to {0, 1}* that are computable in sequential time n^O(1)." --Robin (talk) 18:51, 9 September 2009 (UTC)

That's how Greenlaw and Hoover and another book define it. On the other hand, Elaine Rich, the zoo, and our FP (complexity) define it as "A binary relation P(x,y) is in FP if and only if there is a deterministic polynomial time algorithm that, given x, can find some y such that P(x,y) holds." So it's a set of binary relations that need not be functions according to this def. YMMV. Pcap ping 20:23, 9 September 2009 (UTC)