<p>Formally, the class of <em>functions</em> that can be computed in polynomial time is called <a href="http://en.wikipedia.org/wiki/FP_(complexity)" rel="nofollow"> FP</a>.  People often say "P" instead of "FP" since the distinction is just syntactic and no real confusion will happen.</p>

CC BY-SA 2.5
2010-09-28T18:11:53.353Z
2010-09-28T18:23:03.097Z
2010-09-28T18:23:03.097Z
Noam
<p>A very similar question has already been asked in the topic "<a href="https://cstheory.stackexchange.com/q/1088/">FNP complexity class</a>." There, the questioner essentially asked the difference between the NP and FNP complexity classes. You are asking the difference between the P and FP complexity classes. In short, P and NP are decision classes, while the "F"-versions (FP and FNP) are function classes. For more info, please refer to the topic cited above.</p>

CC BY-SA 2.5
2010-09-28T18:43:11.707Z
2010-09-28T18:43:11.707Z
2017-04-13T12:32:28.053Z
Sadeq Dousti
<p>Problems requiring a solution can be turned into decision problems if there is some way to measure how good a solution is.  The decision version specifies that any solution must be better than some threshold value.  For instance, the decision version of LINEAR PROGRAMMING is obtained by asking if the linear program is feasible.</p>

CC BY-SA 2.5
2010-09-28T18:01:00.577Z
Ah, I'm actually unaware of this -- is deciding whether there's any feasible solution more common than deciding if there's a feasible solution of a certain value?
Daniel Apon
CC BY-SA 2.5
2010-09-28T18:57:14.660Z
Garey and Johnson mention that the two formulations are equivalent (p.288).  LP often has the stipulation that $CX \ge B$, where $X$ is the vector being sought, $C$ is the vector of weights, and $B$ is the desired value.  The point is that the instance with $-CX \le -B$ added to the constraints is feasible iff there is a solution with $CX \ge B$.
András Salamon
CC BY-SA 2.5
2010-09-28T17:54:47.530Z
2010-09-28T17:54:47.530Z
András Salamon
<p>You are right: formally P includes only decision problems. But many decision problems have corresponding optimization problems: find the size of the largest matching in a graph, find the length of the shortest path from s to t in a graph, etc. </p>

<p>Often, these can be reduced to decision problems by instead asking: "Does the graph have a matching using more than k edges?" or "Is there an s->t path of length less than k?" </p>

<p>Obviously, if you can solve the optimization problem, you can solve the decision problem. The converse is also often true, up to logarithmic factors. If you want to know the size of the largest matching in a graph, for example, you can make repeated calls to your algorithm for the decision problem "Does the graph have a matching using more than k edges?" and do binary search on the value "k". In this way, you will require at most log(m) calls, where m is the number of edges. For most problems there is an analogous reduction.</p>

CC BY-SA 2.5
2010-09-28T17:57:04.967Z
To go along with Aaron's answer, linear programming can be formulated as a decision problem by specifying some bound, k, that you're interested in; this is a common trick. For example, is there an assignment of values to variables of the objective function such that you satisfy all the linear constraints AND such that the objective function has value greater than or equal (resp., less than or equal to) k? You can, for instance, decide this in polynomial time by maximizing/minimizing the objective function.
Daniel Apon
CC BY-SA 2.5
2010-09-28T19:50:52.497Z
So essentially, if you know "is there a solution to X?" is in P, then *usually* (but not always) the problem " *what* is the solution to X?" will be solvable in polynomial time?
Xodarap
CC BY-SA 2.5
2010-09-28T20:50:06.670Z
Xodarap: thats right. Usually the ability to solve the decision problem quickly lets you solve the search problem quickly, but not always. As a famous counterexample: By Nash's theorem, every matrix game has a mixed Nash equilibrium, so solving the decision problem "Does this game have a Nash equilibrium" is trivial -- the answer is yes. But it is thought to be hard to actually -find- a Nash equilibrium in a generic game.
Aaron Roth
CC BY-SA 2.5
2010-09-29T04:17:07.850Z
another example of this is Radon's theorem. Given any d+2 points in R^d, there exists a partition of the points into two sets such that the two convex hulls intersect. Easy to verify a candidate partition, but hard to find one.
Suresh Venkat
CC BY-SA 2.5
2010-09-28T17:52:34.257Z
2010-09-28T17:52:34.257Z
Aaron Roth
<p>(I am in the middle of my first theoretical cs course, so I apologize in advance for what is probably a stupid question.)</p>

<p>So, we say that some language L is in P, which means that a Turing machine can be constructed which outputs a 1 if x is in L and 0 otherwise; in addition, the machine runs in polynomial time. I understand this.</p>

<p>But many people say that there are certain problems in P which do not appear to me to be decision problems; for example, maximizing a function subject to linear constraints. What does it mean that "linear programming" is in P? Surely "find the maximal value" is not a decision problem?</p>

<cc.complexity-theory>
Simple question about decision problems
Xodarap
# Simple question about decision problems

(Asked by: username_0 on 2010-09-28)

(I am in the middle of my first theoretical cs course, so I apologize in advance for what is probably a stupid question.)

So, we say that some language L is in P, which means that a Turing machine can be constructed which outputs a 1 if x is in L and 0 otherwise; in addition, the machine runs in polynomial time. I understand this.

But many people say that there are certain problems in P which do not appear to me to be decision problems; for example, maximizing a function subject to linear constraints. What does it mean that "linear programming" is in P? Surely "find the maximal value" is not a decision problem?

**Tags:** cc.complexity-theory

---

## 4 answers

### Answer by username_5 on 2010-09-28. Score: 16 | Accepted answer

You are right: formally P includes only decision problems. But many decision problems have corresponding optimization problems: find the size of the largest matching in a graph, find the length of the shortest path from s to t in a graph, etc.

Often, these can be reduced to decision problems by instead asking: "Does the graph have a matching using more than k edges?" or "Is there an s->t path of length less than k?"

Obviously, if you can solve the optimization problem, you can solve the decision problem. The converse is also often true, up to logarithmic factors. If you want to know the size of the largest matching in a graph, for example, you can make repeated calls to your algorithm for the decision problem "Does the graph have a matching using more than k edges?" and do binary search on the value "k". In this way, you will require at most log(m) calls, where m is the number of edges. For most problems there is an analogous reduction.

> **Comments:**
> **username_4**: To go along with Aaron's answer, linear programming can be formulated as a decision problem by specifying some bound, k, that you're interested in; this is a common trick. For example, is there an assignment of values to variables of the objective function such that you satisfy all the linear constraints AND such that the objective function has value greater than or equal (resp., less than or equal to) k? You can, for instance, decide this in polynomial time by maximizing/minimizing the objective function.  
> **username_0**: So essentially, if you know "is there a solution to X?" is in P, then *usually* (but not always) the problem " *what* is the solution to X?" will be solvable in polynomial time?  
> **username_5**: Xodarap: thats right. Usually the ability to solve the decision problem quickly lets you solve the search problem quickly, but not always. As a famous counterexample: By Nash's theorem, every matrix game has a mixed Nash equilibrium, so solving the decision problem "Does this game have a Nash equilibrium" is trivial -- the answer is yes. But it is thought to be hard to actually -find- a Nash equilibrium in a generic game.  
> **username_6**: another example of this is Radon's theorem. Given any d+2 points in R^d, there exists a partition of the points into two sets such that the two convex hulls intersect. Easy to verify a candidate partition, but hard to find one.  

---

### Answer by username_1 on 2010-09-28. Score: 11

Formally, the class of *functions* that can be computed in polynomial time is called  [FP](http://en.wikipedia.org/wiki/FP_(complexity)). People often say "P" instead of "FP" since the distinction is just syntactic and no real confusion will happen.


---

### Answer by username_2 on 2010-09-28. Score: 8

A very similar question has already been asked in the topic "[FNP complexity class](https://cstheory.stackexchange.com/q/1088/)." There, the questioner essentially asked the difference between the NP and FNP complexity classes. You are asking the difference between the P and FP complexity classes. In short, P and NP are decision classes, while the "F"-versions (FP and FNP) are function classes. For more info, please refer to the topic cited above.


---

### Answer by username_3 on 2010-09-28. Score: 7

Problems requiring a solution can be turned into decision problems if there is some way to measure how good a solution is. The decision version specifies that any solution must be better than some threshold value. For instance, the decision version of LINEAR PROGRAMMING is obtained by asking if the linear program is feasible.

> **Comments:**
> **username_4**: Ah, I'm actually unaware of this -- is deciding whether there's any feasible solution more common than deciding if there's a feasible solution of a certain value?  
> **username_3**: Garey and Johnson mention that the two formulations are equivalent (p.288).  LP often has the stipulation that $CX \ge B$, where $X$ is the vector being sought, $C$ is the vector of weights, and $B$ is the desired value.  The point is that the instance with $-CX \le -B$ added to the constraints is feasible iff there is a solution with $CX \ge B$.  

---

