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$
  • 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 Jan 6 '18 at 3:12
  • $\begingroup$ Every computable function from reals to integers is constant. $\endgroup$ – Andrej Bauer Jan 25 '18 at 7:12
  • 1
    $\begingroup$ Andrej, that is in a different model of computation. $\endgroup$ – Kristoffer Arnsfelt Hansen Jan 25 '18 at 8:11
  • $\begingroup$ Aaand now I no longer believe his earlier paper. $\endgroup$ – Jeffε Jan 30 '18 at 1:52
4
$\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$
  • $\begingroup$ what is the connection to $PSPACE\in P$ or $\#P\in FP$? $\endgroup$ – Turbo Jan 25 '18 at 11:06

Your Answer

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

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