Complexity class of problems solvable in polynomial-time which are not decision problems

0
votes

Complexity class P ~ set of all decision problems that can be solved by a deterministic Turing machine in polynomial time. A decision problem is a problem which can be stated as a yes/no question.

So how would you formally classify problems such as:

  • find the maximum number in an unsorted list of length n?
  • what is the shortest path in a weighted, undirected graph?

Clearly these problems can be solved in polynomial time, but they are not decision problems.

This however is different for NP-complete versus NP-hard problems. Example (TSP):

  • TSP (decision version): does there exist a tour that visits all cities, and costs less than L? (NP-complete)
  • TSP (optimization version): what is the shortest tour that visits all cities? (NP-hard).

In other words, the class of NP-hard problems is not restricted to decision problems; it can also contain search or optimization problems. So why do most (all?) definitions of complexity class P limit the definition to decision problems?

1
time-complexitycomplexity-theory
Possibly this is the convention because the decision problem cannot be harder than the corresponding optimization problem, and the set of decision problems solvable in polynomial time may be thought of as "easy enough" not to merit discerning even easier classes. Polynomial-time optimization problems have corresponding decision problems that are no harder and maybe easier, so maybe there's just no interest in doing it. - Patrick87
For your first question, the class of problems you're looking for is function problems - problems solvable in polynomial time where the output may be more complex than yes/no answers. They have a corresponding complexity class FP. - roctothorpe

1 Answers

0
votes

Because any optimization problem can be converted into multiple decision problems in P. If your question is what is the shortest tour that visits all cities, you can convert this into n decision problems.

Does there exist a tour that visits all cities, and costs less than n?

Does there exist a tour that visits all cities, and costs less than n-1?

Does there exist a tour that visits all cities, and costs less than n-2?

Because there are at most n different options, converting an optimization problem into a decision problem can take place in polynomial time. Therefore, if a decision problem is in P, the corresponding optimization problem is also in P.

Also, an NP-complete problem is just an NP-hard problem that is also in NP. It has nothing to do with whether or not the problem is a decision problem or an optimization problem.