16
$\begingroup$

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?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
18
$\begingroup$

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

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

I believe FP is what you're looking for.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$
    – Mitch
    Apr 13, 2011 at 21:31
  • $\begingroup$ 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. $\endgroup$
    – Nicholas Mancuso
    Apr 13, 2011 at 21:36
  • $\begingroup$ 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. $\endgroup$
    – Mitch
    Apr 13, 2011 at 21:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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