Talk:Function problem

From Wikipedia, the free encyclopedia

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.

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