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

$\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$ Jan 6, 2018 at 3:12
  • $\begingroup$ Every computable function from reals to integers is constant. $\endgroup$ Jan 25, 2018 at 7:12
  • 1
    $\begingroup$ Andrej, that is in a different model of computation. $\endgroup$ Jan 25, 2018 at 8:11
  • $\begingroup$ Aaand now I no longer believe his earlier paper. $\endgroup$
    – Jeffε
    Jan 30, 2018 at 1:52

1 Answer 1

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.

$\endgroup$
2
  • $\begingroup$ what is the connection to $PSPACE\in P$ or $\#P\in FP$? $\endgroup$
    – Turbo
    Jan 25, 2018 at 11:06
  • $\begingroup$ can you address the comment? $\endgroup$
    – Turbo
    Sep 18, 2019 at 22:08

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.