Sortuje

W ostatnim przedruku https://arxiv.org/abs/1801.00776 twierdzi się, że liczb rzeczywistych można posortować w czasie $n$ i przestrzeń liniowa. Artykuł wydaje się rozsądny, chociaż nie jestem ekspertem w dziedzinie algorytmów sortowania.

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

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

Jeśli jest poprawny, byłoby to, moim zdaniem, znaczące, przynajmniej teoretycznie.

Przedstawienie głównego argumentu jest jednak nieco nieformalne i nietradycyjne.

Czy ktoś zauważył / skomentował ten artykuł? Wydaje się, że ten sam autor, Yijie Han, opublikował podobny wynik dotyczący sortowania liczb całkowitych, jak omówiono w czasie Hana , przestrzeni liniowej, algorytmie sortowania liczb całkowitych $O(n \log\log n)$

cc.complexity-theory ds.algorithms sorting kodlu
źródło

v

$v$

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

$int(v \cdot 2^a)$

a

$a$

Każda funkcja obliczalna od liczb rzeczywistych do liczb całkowitych jest stała.

Andrej Bauer,

Andrej, to jest w innym modelu obliczeń.

Kristoffer Arnsfelt Hansen

A teraz nie wierzę już jego wcześniejszej pracy.

Jeffε

Odpowiedzi:

Na podstawie bardzo pomocnego komentarza Sasho Nikolova wydaje się, że oba artykuły wykorzystują podobne modele złożoności, które prowadzą do nieuzasadnionych wniosków, takich jak implikacja, że każdy problem w PSPACE lub #P można rozwiązać w czasie wielomianowym.

Z zadowoleniem przyjmuję wszelkie komentarze, które mogą prowadzić do modyfikacji tej niepewnej odpowiedzi.

kodlu
źródło

P S P A C E \in P

$PSPACE\in P$

# P \in F P

$\#P\in FP$

czy możesz odnieść się do komentarza?

T ....