<p>I believe <a href="http://en.wikipedia.org/wiki/FP_%28complexity%29" rel="nofollow">FP</a> is what you're looking for.</p>

CC BY-SA 3.0
2011-04-13T21:31:03.073Z
Well, I'm rather looking for the relevant decision complexity class rather than the functional one, but even so, I'm fairly certain tha comparison sorting is no where near P-complete (or FP-complete), so I'm expecting a smaller class for which it is expected to be in/complete for.
Mitch
CC BY-SA 3.0
2011-04-13T21:36:47.407Z
I wasn't aware that completeness was one of the requirements to your question. As a decision problem (if you disregard your completeness constraint) why would P not be acceptable as an answer? Given a DTM you can both produce and validate a certificate in polynomial time.
Nicholas Mancuso
CC BY-SA 3.0
2011-04-13T21:44:18.307Z
Given a general problem, what I usually want to know is not just that it is polynomial time, but the smallest class it could be in. I'd like to know if it is in LOGCFL, NL, L, AC_0, etc. Completeness is one way that you "can't" do any better. So nit's not a requirement of my question, but a likely thing to be in an answer.
Mitch
CC BY-SA 3.0
2011-04-13T21:24:51.547Z
2011-04-13T21:24:51.547Z
Nicholas Mancuso
<p>The sorting problem is actually <em>complete</em> for <a href="http://en.wikipedia.org/wiki/TC0">$\mathsf{TC}^0$</a> (under $\mathsf{AC}^0$-reduction). A standard source for this is Section 1.4.3 of <a href="http://rads.stackoverflow.com/amzn/click/3642083986">Vollmer's book</a>. </p>

<p>Note that $\mathsf{TC}^0$ is the class of decision problems, but we usually think of sorting as a function problem, i.e., we want to output the numbers, say, in nondecreasing order. However, we can also define sorting as a decision problem as follows:</p>

<blockquote>
  <p>Given a sequence of numbers $a_1,\ldots,a_n$ and two numbers $k,p\in [n]$, we want to decide if $a_k$ is at position $p$ in the sequence we get by sorting $a_1,\ldots,a_n$ in nondecreasing order. Note that to avoid ambiguity, when $a_i=a_j$, we want $a_i$ to precede $a_j$ if $i&lt;j$.</p>
</blockquote>

CC BY-SA 3.0
2011-04-13T22:35:26.763Z
Excellent...specified as what formal decision problem?
Mitch
CC BY-SA 3.0
2011-04-13T22:40:07.300Z
It would be double excellent to include a reference in your answer.
Oleksandr Bondarenko
CC BY-SA 3.0
2011-04-13T22:57:16.907Z
@Mitch and @Okeksandr: Thanks for your comments! I've just extended my answer to clarify those points.
Dai Le
CC BY-SA 3.0
2011-04-14T00:36:19.927Z
That sounds like the decision problem for order statistics. Is there a related problem where everything is in its right place? Something like given a sequence $a_1...a_n$ and a permutation $\sigma$ on $[1..n]$, decides if $\forall_{1\le k\lt j\le n}, a_{\sigma_k} < a_{\sigma_j}$. This is as hard as yours; is it harder or complete for an including class?
Mitch
CC BY-SA 3.0
2011-04-14T01:27:00.870Z
@Mitch: I believe that checking if everything is in the right place like that is actually easier than sorting. The intuition is that you can check that $a_{\sigma_k}<a_{\sigma_j}$ for all the possible pair $(a_{\sigma_k},a_{\sigma_j})$ with $k<j$ in parallel, which I believe can be done in $\mathsf{AC}^0$. For the above sorting problem, you need to able to "count" to figure out  the right position of a number in the linear ordering.
Dai Le
CC BY-SA 3.0
2011-04-14T14:42:53.017Z
Wow, really? I think I over did it with all pairs. Checking that the permutation is right should really be checking the linear order: $\forall_{k=1}^{n-1} a_{\sigma_k} \lt a_{\sigma_{k+1}}$, but presumably that really makes it even easier so still in $AC_0$
Mitch
CC BY-SA 3.0
2011-04-13T22:33:19.417Z
2011-04-13T23:01:03.890Z
2011-04-13T23:01:03.890Z
Dai Le
<p>Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you <em>can</em> do something (with given restricted resources), and complexity is about showing that you <em>cannot</em> do it without some minimal resources.</p>

<p>So often an algorithmic problem is stated in a decision model in order to place it in a complexity class.</p>

<p>But something that's always bothered me is that some elementary algorithms are never mentioned outright as belonging to a particular class. One example is (comparison) sorting. Try as I might, a relevant class just seems too deficient (really, is it just checking in logspace that the result is sorted? That just seems too weak, or I'm not getting the decision version right).</p>

<p>What is the best/most appropriate/most useful complexity class that comparison sorting lies in?</p>

<cc.complexity-theory><sorting>
Complexity class corresponding to sorting
Mitch
# Complexity class corresponding to sorting

(Asked by: username_0 on 2011-04-13)

Two parts of TCS are algorithms and complexity. I'll simplistically say that algorithms is the study of upper bounds, showing that you *can* do something (with given restricted resources), and complexity is about showing that you *cannot* do it without some minimal resources.

So often an algorithmic problem is stated in a decision model in order to place it in a complexity class.

But something that's always bothered me is that some elementary algorithms are never mentioned outright as belonging to a particular class. One example is (comparison) sorting. Try as I might, a relevant class just seems too deficient (really, is it just checking in logspace that the result is sorted? That just seems too weak, or I'm not getting the decision version right).

What is the best/most appropriate/most useful complexity class that comparison sorting lies in?

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


---

## 2 answers

### Answer by username_2 on 2011-04-13. Score: 18 | Accepted answer

The sorting problem is actually *complete* for [$\mathsf{TC}^0$](http://en.wikipedia.org/wiki/TC0) (under $\mathsf{AC}^0$-reduction). A standard source for this is Section 1.4.3 of [Vollmer's book](http://rads.stackoverflow.com/amzn/click/3642083986).

Note that $\mathsf{TC}^0$ is the class of decision problems, but we usually think of sorting as a function problem, i.e., we want to output the numbers, say, in nondecreasing order. However, we can also define sorting as a decision problem as follows:

> Given a sequence of numbers $a\_1,\ldots,a\_n$ and two numbers $k,p\in [n]$, we want to decide if $a\_k$ is at position $p$ in the sequence we get by sorting $a\_1,\ldots,a\_n$ in nondecreasing order. Note that to avoid ambiguity, when $a\_i=a\_j$, we want $a\_i$ to precede $a\_j$ if $i

> **Comments:**
> **username_0**: Excellent...specified as what formal decision problem?  
> **username_3**: It would be double excellent to include a reference in your answer.  
> **username_2**: @username_0 and @Okeksandr: Thanks for your comments! I've just extended my answer to clarify those points.  
> **username_0**: That sounds like the decision problem for order statistics. Is there a related problem where everything is in its right place? Something like given a sequence $a_1...a_n$ and a permutation $\sigma$ on $[1..n]$, decides if $\forall_{1\le k\lt j\le n}, a_{\sigma_k} < a_{\sigma_j}$. This is as hard as yours; is it harder or complete for an including class?  
> **username_2**: @username_0: I believe that checking if everything is in the right place like that is actually easier than sorting. The intuition is that you can check that $a_{\sigma_k}<a_{\sigma_j}$ for all the possible pair $(a_{\sigma_k},a_{\sigma_j})$ with $k<j$ in parallel, which I believe can be done in $\mathsf{AC}^0$. For the above sorting problem, you need to able to "count" to figure out  the right position of a number in the linear ordering.  
> **username_0**: Wow, really? I think I over did it with all pairs. Checking that the permutation is right should really be checking the linear order: $\forall_{k=1}^{n-1} a_{\sigma_k} \lt a_{\sigma_{k+1}}$, but presumably that really makes it even easier so still in $AC_0$  

---

### Answer by username_1 on 2011-04-13. Score: 0

I believe [FP](http://en.wikipedia.org/wiki/FP_%28complexity%29) is what you're looking for.

> **Comments:**
> **username_0**: Well, I'm rather looking for the relevant decision complexity class rather than the functional one, but even so, I'm fairly certain tha comparison sorting is no where near P-complete (or FP-complete), so I'm expecting a smaller class for which it is expected to be in/complete for.  
> **username_1**: I wasn't aware that completeness was one of the requirements to your question. As a decision problem (if you disregard your completeness constraint) why would P not be acceptable as an answer? Given a DTM you can both produce and validate a certificate in polynomial time.  
> **username_0**: Given a general problem, what I usually want to know is not just that it is polynomial time, but the smallest class it could be in. I'd like to know if it is in LOGCFL, NL, L, AC_0, etc. Completeness is one way that you "can't" do any better. So nit's not a requirement of my question, but a likely thing to be in an answer.  

---

