Возможна ли сортировка действительных чисел во времени и линейном пространстве?

В недавнем препринте https://arxiv.org/abs/1801.00776 утверждается, что вещественных чисел можно отсортировать по времени и линейному пространству. Статья кажется разумной, хотя я не эксперт в алгоритмах сортировки. $n$

O (n \sqrt{\log n}),

$O(n \sqrt{\log n}),$

Если это правильно, это будет значительным, я думаю, по крайней мере, теоретически.

Однако представление основного аргумента несколько неформально и нетрадиционно.

Кто-нибудь заметил / прокомментировал эту статью? Похоже, что тот же автор, Иджи Хан, опубликовал связанный результат по целочисленной сортировке, как обсуждалось в Хана , линейном пространстве, алгоритме целочисленной сортировки. $O(n \log\log n)$

cc.complexity-theory ds.algorithms sorting kodlu
источник

«Мы предполагаем, что переменная содержащая действительное значение, имеет произвольную точность, и для неотрицательного целого числа может быть вычислено за постоянное время». Это пахнет подозрительно, см. Computational-geometry.org/mailing-lists/compgeom-announce/…

v

$v$

i n t (v \cdot 2^{a})

$int(v \cdot 2^a)$

a

$a$

Сашо Николов

Каждая вычислимая функция от вещественных чисел до целых постоянна.

Андрей Бауэр

Андрей, это в другой модели вычислений.

Кристоффер Арнсфельт Хансен

Теперь я больше не верю его предыдущей статье.

Джефф

Ответы:

Исходя из очень полезного комментария Сашо Николова, кажется, что обе статьи используют одинаковые модели сложности, которые приводят к необоснованным выводам, таким как вывод о том, что любая проблема в PSPACE или #P может быть решена за полиномиальное время.

Я приветствую любые комментарии, которые могут привести к изменению этого предварительного ответа.

kodlu
источник

какая связь с или ?

P S P A C E \in P

$PSPACE\in P$

# P \in F P

$\#P\in FP$

T ....

Вы можете обратиться к комментарию?

T ....