# Complexity class corresponding to sorting

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?

The sorting problem is actually complete for $\mathsf{TC}^0$ (under $\mathsf{AC}^0$-reduction). A standard source for this is Section 1.4.3 of Vollmer's book.

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<j$.

• Excellent...specified as what formal decision problem? – Mitch Apr 13 '11 at 22:35
• It would be double excellent to include a reference in your answer. – Oleksandr Bondarenko Apr 13 '11 at 22:40
• @Mitch and @Okeksandr: Thanks for your comments! I've just extended my answer to clarify those points. – Dai Le Apr 13 '11 at 22:57
• 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 Apr 14 '11 at 0:36
• @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 Apr 14 '11 at 1:27

I believe FP is what you're looking for.

• 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 Apr 13 '11 at 21:31
• 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 Apr 13 '11 at 21:36
• 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 Apr 13 '11 at 21:44