Está ordenando

En la preimpresión reciente https://arxiv.org/abs/1801.00776 , se afirma que números reales se pueden ordenar en el tiempo $n$ y espacio lineal. El artículo parece razonable, aunque no soy un experto en algoritmos de clasificación.

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

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

Si es correcto, esto sería significativo, creo, al menos teóricamente.

Sin embargo, la presentación del argumento principal es algo informal y no tradicional.

¿Alguien ha notado / comentado en este documento? Parece que el mismo autor, Yijie Han, ha publicado un resultado relacionado sobre la ordenación de enteros, como se discutió en el algoritmo de ordenación de enteros tiempo, espacio lineal, entero $O(n \log\log n)$

cc.complexity-theory ds.algorithms sorting kodlu
fuente

v

$v$

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

$int(v \cdot 2^a)$

a

$a$

Cada función computable desde reales a enteros es constante.

Andrej Bauer el

Andrej, eso está en un modelo diferente de computación.

Kristoffer Arnsfelt Hansen

Y ahora ya no creo en su artículo anterior.

Jeffε

Respuestas:

Basado en el comentario muy útil de Sasho Nikolov, parece que ambos documentos usan modelos similares de complejidad que conducen a conclusiones irrazonables, como la implicación de que cualquier problema en PSPACE o #P puede resolverse en tiempo polinómico.

Agradezco cualquier comentario que pueda conducir a una modificación de esta respuesta tentativa.

kodlu
fuente

P S P A C E \in P

$PSPACE\in P$

# P \in F P

$\#P\in FP$

puedes abordar el comentario?

T ....