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 articles
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of
Computer science related articles 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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
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).reply
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)reply
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]...
Pcapping 15:40, 7 September 2009 (UTC)reply
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)reply
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.
Pcapping 22:53, 7 September 2009 (UTC)reply
For instance, Arora and Barak, Cambridge University Press, 2009,
ISBN978-0-521-42426-4 make no reference to "function problem", or even FP and FNP.
Pcapping 10:44, 8 September 2009 (UTC)reply
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)reply
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 citation needed after the "function problem" term in hope some finds a ref, or takes clue and writes it in a book :-)
Pcapping 14:26, 8 September 2009 (UTC)reply
There are several reasonable references in the first couple pages of this search:
[4]. — Carl (
CBM ·
talk) 21:25, 8 September 2009 (UTC)reply
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.
Pcapping 23:22, 8 September 2009 (UTC)reply
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".
Pcapping 00:16, 9 September 2009 (UTC)reply
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...
Pcapping 00:21, 9 September 2009 (UTC)reply
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...
Pcapping 00:39, 9 September 2009 (UTC)reply
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 nO(1)." --
Robin (
talk) 18:51, 9 September 2009 (UTC)reply
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.
Pcapping 20:23, 9 September 2009 (UTC)reply
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 articles
This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of
Computer science related articles 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.Computer scienceWikipedia:WikiProject Computer scienceTemplate:WikiProject Computer scienceComputer science articles
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).reply
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)reply
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]...
Pcapping 15:40, 7 September 2009 (UTC)reply
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)reply
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.
Pcapping 22:53, 7 September 2009 (UTC)reply
For instance, Arora and Barak, Cambridge University Press, 2009,
ISBN978-0-521-42426-4 make no reference to "function problem", or even FP and FNP.
Pcapping 10:44, 8 September 2009 (UTC)reply
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)reply
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 citation needed after the "function problem" term in hope some finds a ref, or takes clue and writes it in a book :-)
Pcapping 14:26, 8 September 2009 (UTC)reply
There are several reasonable references in the first couple pages of this search:
[4]. — Carl (
CBM ·
talk) 21:25, 8 September 2009 (UTC)reply
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.
Pcapping 23:22, 8 September 2009 (UTC)reply
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".
Pcapping 00:16, 9 September 2009 (UTC)reply
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...
Pcapping 00:21, 9 September 2009 (UTC)reply
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...
Pcapping 00:39, 9 September 2009 (UTC)reply
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 nO(1)." --
Robin (
talk) 18:51, 9 September 2009 (UTC)reply
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.
Pcapping 20:23, 9 September 2009 (UTC)reply