Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

Question

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

"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 http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-December/000852.html — Sasho Nikolov, Jan 06 '18 at 03:12
Every computable function from reals to integers is constant. — Andrej Bauer, Jan 25 '18 at 07:12

score 5 · Answer 1 · answered Jan 22 '18 at 18:35

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.

Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

1 Answers1