7
$\begingroup$

Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time.

Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done in linear time using $\{\times,+,-,\bmod\}$ operations in unit cost RAM model where ring operations can be performed on arbitrarily large words in unit time?

I am thinking of using only $!=0$ comparison using modulo operations. If $x>y$, then $x\bmod y\neq x$. If $x<y$, then $x\bmod y=x$ holds. So using $x-y==0$ followed by $x - (x\bmod y)==0$ will tell if $x<y$. I do not wish to have bit operations. I want more like $\mathsf{BSS}$ model.

Let me clarify my sorting problem further.

Say I have been given list of $n$ different integers $a_0,\dots,a_n$ with each $a_i\in(0,2^m-1)$. I can write down the list in a long integer form $$G=a_0+a_12^m+\dots+a_n2^{nm}$$

There is an unique permutation $\sigma\in S_{n+1}$ such $$N=a_{\sigma(0)}+a_{\sigma(1)}2^m+\dots+a_{\sigma(n)}2^{nm}$$ is minimum.

How many ring operations (with $\bmod$) would it take in worst case for converting integer $G$ to $N$?

$\endgroup$
  • 2
    $\begingroup$ If you do not allow mod operations, then Ben-or 1983 gives an $\Omega(n \log n)$ lower bound on algebraic decision trees for sorting. Ben-Or's proof is for real numbers; in the same model, but restricted to integer inputs, the same result holds by Yao 1989 and Lubiw and Racz. But we know that having mod operations can change things quite a bit, so this is really just FYI. $\endgroup$ – Joshua Grochow Aug 14 '15 at 17:28
  • $\begingroup$ @JoshuaGrochow Just curious, what is the arithmetic complexity of $\bmod$ operation assuming using only $\{\times,+,-\}$ operations assuming inputs are bounded by say $T$ number of bits? Can we do bit operations at all in such a model? If you do not bound by $T$ number of bits, it is plausible you can do $\bmod$ by 'general' comparison in linear time. However does $\bmod$ remain linear time if we only allow $!=0$ comparison (looks like it is possible but not sure). That is why I wrote $\bmod$ separately. In that context why doesn't Ben-Or 1983 result give $\Omega(n\log n)$ as true lower bound? $\endgroup$ – user34945 Aug 14 '15 at 18:10
  • $\begingroup$ If all you have is $+,-,\times,\leq$, then mod can be done in something like $O(T)$ operations for integers of bitlength $T$, using repeated addition (the $+$ analogue of repeated squaring). The issue is that in those models, the non-uniformity doesn't know about bitlength, only about the number of elements. If the non-uniformity can be in both number of elements and total bitlength, then you are indeed essentially back to the Boolean world. (This is the crucial distinction for Mulmuley's result in the "PRAM model without bit operations", which knows about bitlength.) $\endgroup$ – Joshua Grochow Aug 15 '15 at 3:02
  • $\begingroup$ How do you intend to define mod for such a class of rings? As far as I can see, the conditions do not imply that for every $x>0$ and $y$, there is $0\le z<x$ such that $z\equiv y\pmod x$, which is what I would expect to be the natural definition. On the other hand, what is the point of requiring the ring to be a gcd domain if you do not use the gcd's in any way? $\endgroup$ – Emil Jeřábek May 24 '16 at 9:35
  • $\begingroup$ Hang on, I would also need the $z$ to be uniquely determined by the above congruence so that $y\bmod x$ is a well defined operation. Now, the uniqueness of $z$ is equivalent to the ring being discretely ordered. $\endgroup$ – Emil Jeřábek May 24 '16 at 9:47
5
$\begingroup$

This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible.

I think you're going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory indexing? Comparisons? If you allow bitwise binary operations (including shifts) and either hashing or unbounded memory then it's all over, even without multiplication or division:

def sort(intlist):
    backtrans = {}
    bits = 0
    for x in intlist:
        y = 1<<x
        if y in backtrans:
            backtrans[y][1] += 1
        else:
            backtrans[y] = [x,1]
        bits |= y
    while bits:
        y = bits &~ (bits - 1)
        x,reps = backtrans[y]
        for i in range(reps):
            yield x
        bits &=~ y

There's also a linear time sorting algorithm (for large enough machine words) by Albers and Hagerup 1997 but I'm not sure which operations it needs or whether it could be adapted to use only arithmetic and not bit manipulation. The reference is:

Albers, Susanne; Hagerup, Torben (1997), "Improved parallel integer sorting without concurrent writing", Information and Computation 136 (1): 25–51.

$\endgroup$
  • 1
    $\begingroup$ I think a reasonable variant of the question would be the following: you can do memory indexing, there is unbounded memory initialised to zeroes, you can do comparisons, but you can't use bitwise operations (which are essentially linear scanning in disguise). $\endgroup$ – Jukka Suomela Aug 14 '15 at 10:24
  • $\begingroup$ @DavidEppstein I am thinking of using $==$ comparison using modulo operations. If $x>y$, then $x\bmod y\neq x$. If $x<y$, then $x\bmod y=x$ holds. I do not wish to have bit operations. I want more like $\mathsf{BSS}$ model. $\endgroup$ – user34945 Aug 14 '15 at 12:20

Your Answer

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