Está ordenando

Na recente pré-impressão https://arxiv.org/abs/1801.00776 , afirma-se que números reais podem ser classificados no tempo $n$ e no espaço linear. O artigo parece razoável, embora eu não seja especialista em algoritmos de classificação.

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

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

Se correto, isso seria significativo, acredito, pelo menos teoricamente.

A apresentação do argumento principal é um tanto informal e não tradicional, no entanto.

Alguém notou / comentou este artigo? Parece que o mesmo autor, Yijie Han, publicou um resultado relacionado à classificação inteira, conforme discutido em Han , tempo, espaço linear, algoritmo de classificação inteira $O(n \log\log n)$

cc.complexity-theory ds.algorithms sorting kodlu
fonte

v

$v$

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

$int(v \cdot 2^a)$

a

$a$

Toda função computável de reais a inteiros é constante.

Andrej Bauer

Andrej, isso está em um modelo diferente de computação.

Kristoffer Arnsfelt Hansen

E agora eu não acredito mais em seu artigo anterior.

Jeffε

Respostas:

Com base no comentário muito útil de Sasho Nikolov, parece que os dois trabalhos usam modelos semelhantes de complexidade que levam a conclusões irracionais, como a implicação de que qualquer problema no PSPACE ou #P pode ser resolvido em tempo polinomial.

Congratulo-me com quaisquer comentários que possam levar a uma modificação desta resposta provisória.

kodlu
fonte

P S P A C E \in P

$PSPACE\in P$

# P \in F P

$\#P\in FP$

você pode endereçar o comentário?

T ....