8
$\begingroup$

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

Improve this question
$\endgroup$

4 Answers 4

Reset to default
16
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Daniel Apon
    Sep 28, 2010 at 17:57
  • $\begingroup$ 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? $\endgroup$
    – Xodarap
    Sep 28, 2010 at 19:50
  • 3
    $\begingroup$ 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. $\endgroup$
    – Aaron Roth
    Sep 28, 2010 at 20:50
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Sep 29, 2010 at 4:17
11
$\begingroup$

Formally, the class of functions that can be computed in polynomial time is called FP. People often say "P" instead of "FP" since the distinction is just syntactic and no real confusion will happen.

Improve this answer
$\endgroup$
8
$\begingroup$

A very similar question has already been asked in the topic "FNP complexity class." 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.

Improve this answer
$\endgroup$
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Daniel Apon
    Sep 28, 2010 at 18:01
  • 1
    $\begingroup$ 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$. $\endgroup$
    – András Salamon
    Sep 28, 2010 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.