<p><strong>SHORT ANSWER</strong>
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).</p>
<p><strong>LONG ANSWER</strong>
There are standard techniques for transforming function and
optimization problems into decision problems (see the <a href="https://en.wikipedia.org/wiki/Decision_problem#Optimization_problems" rel="nofollow noreferrer">Optimization problems</a> section of the Wikipedia page on <a href="https://en.wikipedia.org/wiki/Decision_problem" rel="nofollow noreferrer">Decision Problems</a>): Given an optimization problem <span class="math-container">$O$</span>, the corresponding decision problem <span class="math-container">$D$</span> would be to decide if, for a given instance <span class="math-container">$I$</span> and a threshold <span class="math-container">$t$</span>, the score of an optimal solution <span class="math-container">$OPT_O(I)$</span> is larger than the threshold <span class="math-container">$t$</span>, i.e. if <span class="math-container">$OPT_O(I)&gt;t$</span>.</p>
<p>The time complexity of <span class="math-container">$O$</span> and <span class="math-container">$D$</span> are interdependent:</p>
<ul>
<li><p>Any solution to <span class="math-container">$O$</span> running in time polynomial in the input size yields a solution for <span class="math-container">$D$</span> 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 <span class="math-container">$t$</span>.</p>
</li>
<li><p>Given a solution <span class="math-container">$S$</span> running in time polynomial in the input size to the decision problem <span class="math-container">$D$</span> with threshold <span class="math-container">$t$</span>, one can perform an <a href="https://en.wikipedia.org/wiki/Exponential_search" rel="nofollow noreferrer">Exponential Search</a> for the value <span class="math-container">$OPT$</span> in <span class="math-container">$2\log_2(OPT)$</span> comparisons, where <span class="math-container">$S$</span> is used for each comparisons. This results into an algorithm finding <span class="math-container">$OPT$</span> in time polynomial in the input size even if <span class="math-container">$OPT$</span> is exponential in the input size as the running time is a polynomial multiplied by another polynomial (<span class="math-container">$\log_2(OPT)$</span>).</p>
</li>
</ul>
<p>I hope it helps!</p>

CC BY-SA 4.0
2022-10-02T16:27:45.767Z
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?
ryu576
CC BY-SA 4.0
2022-10-02T23:15:56.887Z
@ryu576, https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time, https://en.wikipedia.org/wiki/FP_(complexity), https://cs.stackexchange.com/q/154473/755
D.W.
CC BY-SA 4.0
2022-10-02T23:24:33.870Z
Thanks, this helps. The last one is my own question :)
ryu576
CC BY-SA 4.0
2022-10-03T12:22:32.500Z
@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?
J.y B.y
CC BY-SA 4.0
2022-10-03T17:09:41.630Z
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)?
ryu576
CC BY-SA 4.0
2022-10-03T17:13:48.963Z
I don't quite get what you mean by sorting an array into another.
ryu576
CC BY-SA 4.0
2022-10-04T15:24:06.537Z
You usually sort RECORDS (e.g. ( (1,Germany), (2,France),(3,Slovaquia),(4,Russia))) rather than just numbers, and sorting a set of records (that above) into another one (e.g. (3,2,1,4)) requires to put the records of the first one in the order of the second one. I hope it is more clear like this?
J.y B.y
CC BY-SA 4.0
2022-10-04T15:25:11.420Z
And yes, the computational problem is AT LEAST as difficult as the decision problem, they are not always equivalent in computational complexity. That make them useful to prove computational lower bounds, but not a panacea.
J.y B.y
CC BY-SA 4.0
2022-10-04T16:08:27.830Z
Got it, this helps. Thanks a lot!
ryu576
CC BY-SA 4.0
2022-10-02T10:16:54.833Z
2022-10-02T10:16:54.833Z
J.y B.y
<p>Looking at many posts on Stack Overflow, it seems the set <span class="math-container">$P$</span> has only decision problems. See for instance the accepted answer <a href="https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard">here</a>.</p>
<p>But, this seems to be in contradiction to the book Introduction to Algorithms by Cormen et.al. In chapter 34, the section titled &quot;NP-completeness and the classes P and NP&quot;, they simply say: &quot;P consists of those problems that are solvable in polynomial time&quot;. They even say later, &quot;NP-completeness applies directly not to optimization problems, but to decision problems&quot; but say no such thing about P and NP. It seems they are implying that optimization problems also lie in <span class="math-container">$P$</span>.</p>
<p>What is the source of this discrepancy? Is it fair to say the Stack Overflow posters are simply mistaken?</p>

CC BY-SA 4.0
2022-10-02T05:15:30.910Z
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.
holf
<cc.complexity-theory><np>
Does the set $P$ contain only decision problems or also optimization problems?
ryu576
# Does the set $P$ contain only decision problems or also optimization problems?

(Asked by: username_0 on 2022-10-02)

Looking at many posts on Stack Overflow, it seems the set $P$ has only decision problems. See for instance the accepted answer [here](https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard).

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?

**Tags:** cc.complexity-theory, np

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2022-10-02. Score: 1 | Accepted answer

**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](https://en.wikipedia.org/wiki/Decision_problem#Optimization_problems) section of the Wikipedia page on [Decision Problems](https://en.wikipedia.org/wiki/Decision_problem)): 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](https://en.wikipedia.org/wiki/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!

> **Comments:**
> **username_0**: 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?  
> **username_3**: @username_0, https://en.wikipedia.org/wiki/Time_complexity#Polynomial_time, https://en.wikipedia.org/wiki/FP_(complexity), https://cs.stackexchange.com/q/154473/755  
> **username_0**: Thanks, this helps. The last one is my own question :)  
> **username_2**: @username_0 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?  
> **username_0**: 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)?  
> **username_0**: I don't quite get what you mean by sorting an array into another.  
> **username_2**: You usually sort RECORDS (e.g. ( (1,Germany), (2,France),(3,Slovaquia),(4,Russia))) rather than just numbers, and sorting a set of records (that above) into another one (e.g. (3,2,1,4)) requires to put the records of the first one in the order of the second one. I hope it is more clear like this?  
> **username_2**: And yes, the computational problem is AT LEAST as difficult as the decision problem, they are not always equivalent in computational complexity. That make them useful to prove computational lower bounds, but not a panacea.  
> **username_0**: Got it, this helps. Thanks a lot!  

---

