-1
$\begingroup$

Looking at many posts on Stack Overflow, it seems the set $P$ has only decision problems. See for instance the accepted answer here.

But, this seems to be in contradiction to the book Introduction to Algorithms by Cormen et.al. In chapter 34, the section titled "NP-completeness and the classes P and NP", they simply say: "P consists of those problems that are solvable in polynomial time". They even say later, "NP-completeness applies directly not to optimization problems, but to decision problems" but say no such thing about P and NP. It seems they are implying that optimization problems also lie in $P$.

What is the source of this discrepancy? Is it fair to say the Stack Overflow posters are simply mistaken?

$\endgroup$
1
  • 5
    $\begingroup$ This is not a research level question, hence not suited to this website. P (and NP) is formally defined as a class of decision problems (check any textbook dealing with complexity theory; the Cormen deals with algorithms). Many definitions do not make sense otherwise. Now, decision is usually not what people are interesting in so they associate decision problem to optimization problems to study their complexity. This is often made implicitly hence the confusion. $\endgroup$
    – holf
    Oct 2 at 5:15

1 Answer 1

1
$\begingroup$

SHORT ANSWER By definition, P and NP are (infinite) sets of decision problems (more exactly, Languages, but let's keep it simple). Studying the decision problem version of computational problem is simpler, always provides good information about lower bounds on their computational complexity, and often provides good information about upper bound on their computational complexity. It is such a basic technique that experienced researchers switch without effort from one version to the others (such as in the answers on SE).

LONG ANSWER There are standard techniques for transforming function and optimization problems into decision problems (see the Optimization problems section of the Wikipedia page on Decision Problems): Given an optimization problem $O$, the corresponding decision problem $D$ would be to decide if, for a given instance $I$ and a threshold $t$, the score of an optimal solution $OPT_O(I)$ is larger than the threshold $t$, i.e. if $OPT_O(I)>t$.

The time complexity of $O$ and $D$ are interdependent:

  • Any solution to $O$ running in time polynomial in the input size yields a solution for $D$ running in time polynomial in the input size (basically, the same time plus that for one single operation, a comparison), by just finding the optimal value and comparing it to the threshold $t$.

  • Given a solution $S$ running in time polynomial in the input size to the decision problem $D$ with threshold $t$, one can perform an Exponential Search for the value $OPT$ in $2\log_2(OPT)$ comparisons, where $S$ is used for each comparisons. This results into an algorithm finding $OPT$ in time polynomial in the input size even if $OPT$ is exponential in the input size as the running time is a polynomial multiplied by another polynomial ($\log_2(OPT)$).

I hope it helps!

$\endgroup$
9
  • $\begingroup$ Thanks. This does help a lot. What is bothering me particularly is that sorting an array is not in P. I’ve been trying to construct a decision problem without success so far. If it’s easy, can you please tell me how to construct it and go back and forth? $\endgroup$
    – ryu576
    Oct 2 at 16:27
  • $\begingroup$ Thanks, this helps. The last one is my own question :) $\endgroup$
    – ryu576
    Oct 2 at 23:24
  • $\begingroup$ @ryu576 Deciding if an array is sorted (or if a given permutation is sorting it) is DEFINITELY in $P$: you need only $n-1$ comparisons to do so. Similarly, deciding if one array can be sorted into another one is also in $P$ when all elements are distinct, solved in time within $O(n\lg n)$ by sorting the first one using the complete order induced by the second one. I think it is still polynomial if the elements have repetitions, but I would need to think more to do a formal proof. Why would you say that the decision problem corresponding to Sorting is not in P? $\endgroup$
    – J..y B..y
    Oct 3 at 12:22
  • $\begingroup$ Yes, but the decision problem for sorting is fundamentally different (easier) than the sorting problem itself which requires tricks like divide and conquer. I was looking for a problem in P that is equivalent to the sorting problem. One lead I got from another question was a decision problem on the number of inversions. It might be that the only way to count inversions is to sort the array (via merge sort)? $\endgroup$
    – ryu576
    Oct 3 at 17:09

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