時間$ O(n sqrt { log n})$と線形空間で$ n $実数をソートしていますか?

最近のプレプリント https://arxiv.org/abs/1801.00776 では、$ n
$実数は時間内にソートすることができます $$ O(n sqrt { log n})、 $$
線形空間である。私はソートアルゴリズムの専門家ではありませんが、論文は合理的です。

正しければ、これは少なくとも理論的には重要であると思います。

しかし、主要議論の提示は、幾分非公式かつ非伝統的である。

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 loglog n)$ time, linear space, integer sorting
algorithm

ベストアンサー

Sasho
Nikolovの非常に有益なコメントに基づいて、両方の論文がPSPACEや#Pの問題が多項式時間で解けるという意味など、不合理な結論につながる同様の複雑なモデルを使用しているようです。

私はこの暫定的な答えの修正につながる可能性のあるコメントを歓迎する。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です