12
$\begingroup$

In the recent preprint https://arxiv.org/abs/1801.00776, it is claimed that $n$ real numbers can be sorted in time $$O(n \sqrt{\log n}), $$ and linear space. The paper seems reasonable, though I am not an expert in sorting algorithms.

If correct, this would be a significant, I believe, at least theoretically.

The presentation of the main argument is somewhat informal and nontraditional, however.

Has anyone noticed/commented on this paper? It seems that the same author, Yijie Han, has published a related result on integer sorting, as discussed in Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

Improve this question
$\endgroup$
4
  • 12
    $\begingroup$ "We assume that a variable $v$ holding a real value has arbitrary precision and $int(v \cdot 2^a)$ for a nonnegative integer $a$ can be computed in constant time." This smells fishy, see computational-geometry.org/mailing-lists/compgeom-announce/… $\endgroup$
    – Sasho Nikolov
    Commented Jan 6, 2018 at 3:12
  • $\begingroup$ Every computable function from reals to integers is constant. $\endgroup$
    – Andrej Bauer
    Commented Jan 25, 2018 at 7:12
  • 1
    $\begingroup$ Andrej, that is in a different model of computation. $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Jan 25, 2018 at 8:11
  • $\begingroup$ Aaand now I no longer believe his earlier paper. $\endgroup$
    – Jeffε
    Commented Jan 30, 2018 at 1:52

1 Answer 1

Reset to default
5
$\begingroup$

Based on Sasho Nikolov's very helpful comment, it seems that both papers use similar models of complexity which lead to unreasonable conclusions, such as the implication that any problem in PSPACE or #P can be solved in polynomial time.

I welcome any comments which may lead to a modification of this tentative answer.

Improve this answer
$\endgroup$
0

Your Answer

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

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