Est-il possible de trier nombres réels dans le temps et l'espace linéaire?

Dans la récente préimpression https://arxiv.org/abs/1801.00776 , il est affirmé que nombres réels peuvent être triés dans le temps et l'espace linéaire. L'article semble raisonnable, même si je ne suis pas un expert en algorithmes de tri. $n$

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

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

Si elle est correcte, ce serait un point important, je crois, du moins théoriquement.

La présentation de l'argument principal est cependant quelque peu informelle et non traditionnelle.

Quelqu'un a-t-il remarqué / commenté ce document? Il semble que le même auteur, Yijie Han, a publié un résultat connexe sur le tri des entiers, comme discuté dans le temps Han , l'espace linéaire, l'algorithme de tri des entiers $O(n \log\log n)$

cc.complexity-theory ds.algorithms sorting kodlu
la source

"Nous supposons qu'une variable contenant une valeur réelle a une précision arbitraire et pour un entier non négatif peut être calculé en temps constant." Cela sent le poisson, voir computational-geometry.org/mailing-lists/compgeom-announce/…

v

$v$

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

$int(v \cdot 2^a)$

a

$a$

Sasho Nikolov

Chaque fonction calculable des réels aux entiers est constante.

Andrej Bauer

Andrej, c'est dans un autre modèle de calcul.

Kristoffer Arnsfelt Hansen

Aaand maintenant je ne crois plus son article précédent.

Jeffε

Réponses:

Sur la base du commentaire très utile de Sasho Nikolov, il semble que les deux articles utilisent des modèles similaires de complexité qui conduisent à des conclusions déraisonnables, telles que l'implication que tout problème dans PSPACE ou #P peut être résolu en temps polynomial.

Je me réjouis de tout commentaire qui pourrait conduire à une modification de cette réponse provisoire.

kodlu
la source

quelle est la connexion à ou ?

P S P A C E \in P

$PSPACE\in P$

# P \in F P

$\#P\in FP$

T ....

pouvez-vous répondre au commentaire?

T ....