<p>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.</p>

<p>I welcome any comments which may lead to a modification of this tentative answer.</p>

CC BY-SA 3.0
2018-01-22T18:35:15.980Z
2018-01-22T18:35:15.980Z
kodlu
<p>In the recent preprint <a href="https://arxiv.org/abs/1801.00776" rel="noreferrer">https://arxiv.org/abs/1801.00776</a>, 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.</p>

<p>If correct, this would be a significant, I believe, at least theoretically.</p>

<p>The presentation of the main argument is somewhat informal and nontraditional, however. </p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/6642/hans-on-log-log-n-time-linear-space-integer-sorting-algorithm">Han&#39;s $O(n \log\log n)$ time, linear space, integer sorting algorithm</a></p>

CC BY-SA 3.0
2018-01-06T03:12:24.427Z
"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
CC BY-SA 3.0
2018-01-25T07:12:21.793Z
Every computable function from reals to integers is constant.
Andrej Bauer
CC BY-SA 3.0
2018-01-25T08:11:36.987Z
Andrej, that is in a different model of computation.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2018-01-30T01:52:23.297Z
Aaand now I no longer believe his earlier paper.
Jeffε
<cc.complexity-theory><ds.algorithms><sorting>
Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?
kodlu
# Is sorting $n$ real numbers in time $O(n \sqrt{\log n})$ and linear space possible?

(Asked by: username_0 on 2018-01-04)

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](https://cstheory.stackexchange.com/questions/6642/hans-on-log-log-n-time-linear-space-integer-sorting-algorithm)

**Tags:** cc.complexity-theory, ds.algorithms, sorting

> **Comments:**
> **username_1**: "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  
> **username_2**: Every computable function from reals to integers is constant.  
> **username_3**: Andrej, that is in a different model of computation.  
> **username_4**: Aaand now I no longer believe his earlier paper.  

---

## 1 answers

### Answer by username_0 on 2018-01-22. Score: 5

Based on username_1'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.


---

