8
$\begingroup$

It is not difficult to show that sorting an array of numbers is hard for $\mathsf{TC^0}$. If the input is an array of 1s and 0s then it is essentially the function $Count$ (given $n$ bits, output the number of 1s in binary) since $Count$ is complete for $\mathsf{TC^0}$ and it is possible to convert unary numbers to binary numbers and (logarithmicly) small binary numbers to unary numbers in $\mathsf{AC^0}$:

$Count(\vec{x}) = Binary(Sort(\vec{x}))$
$Sort(\vec{x}) = Unary(Count(\vec{x}))$

So the power of $\mathsf{TC^0}$ is essentially sorting a binary string (eg. 100011 to 000111). This is true more generally when the numbers in the array are bounded. My question is what if the numbers are not bounded?

Is the problem of sorting an array of unbounded numbers still in $\mathsf{TC^0}$? Is it complete for a larger class like $\mathsf{NC^1}$?

$\endgroup$
  • $\begingroup$ Btw, if you know a reference for "sorting arrays of bits is $\mathsf{TC^0}$-complete" please let me know. $\endgroup$ – Kaveh Oct 17 '12 at 4:51
  • $\begingroup$ Did you check Cook & Nguyen? $\endgroup$ – Yuval Filmus Oct 17 '12 at 5:11
  • 2
    $\begingroup$ @Kaveh, the reduction is in Chandra, Stockmeyer and Vishkin, "Constant Depth Reducibility", SIAM J. Comput. 13 (2), 1984. $\endgroup$ – Jan Johannsen Oct 17 '12 at 13:10
9
$\begingroup$

Suppose you have $n$ numbers $x_1,\ldots,x_n$ of width $m \geq \log n$. Without loss of generality, all numbers are different (add an extra $\log n$ lower-order bits). Two numbers can be compared in AC0, so in AC0 we can compute, for each $x_i$, a binary vector $v$, defined by $v_j = 1$ if $x_j \geq x_i$. In TC0 we can sort $v$ to $w$, and then locate (in AC0) the position $k$ such that $w_k = 1$ while $w_{k-1} = 0$ (where $w_0=0$, $w_{n+1}=1$). Given these values $k$ for each $i \in [n]$, we can compute the sorted array in AC0. In total, we get a TC0 circuit.

$\endgroup$
  • $\begingroup$ nice trick :) (count the number of smaller numbers in the array), thanks Yuval. $\endgroup$ – Kaveh Oct 17 '12 at 15:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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