Mengurutkan

Dalam pracetak https://arxiv.org/abs/1801.00776 baru-baru ini , dinyatakan bahwa bilangan real dapat diurutkan dalam waktu $n$ dan ruang linear. Makalah ini tampaknya masuk akal, meskipun saya bukan ahli dalam menyortir algoritma.

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

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

Jika benar, ini akan menjadi signifikan, saya percaya, setidaknya secara teoritis.

Namun, penyajian argumen utama agak informal dan nontradisional.

Adakah yang memperhatikan / mengomentari makalah ini? Tampaknya penulis yang sama, Yijie Han, telah menerbitkan hasil terkait pada bilangan bulat menyortir, seperti yang dibahas dalam Han waktu, ruang linear, integer algoritma sorting $O(n \log\log n)$

cc.complexity-theory ds.algorithms sorting Kodlu
sumber

v

$v$

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

$int(v \cdot 2^a)$

a

$a$

Setiap fungsi yang dapat dihitung dari real ke integer adalah konstan.

Andrej Bauer

Andrej, yang berada dalam model perhitungan yang berbeda.

Kristoffer Arnsfelt Hansen

Aaand sekarang aku tidak lagi percaya pada makalahnya sebelumnya.

Jeffε

Jawaban:

Berdasarkan komentar Sasho Nikolov yang sangat membantu, tampaknya kedua makalah tersebut menggunakan model kompleksitas yang serupa yang mengarah pada kesimpulan yang tidak masuk akal, seperti implikasi bahwa masalah apa pun di PSPACE atau #P dapat diselesaikan dalam waktu polinomial.

Saya menyambut setiap komentar yang dapat menyebabkan modifikasi jawaban sementara ini.

Kodlu
sumber

P S P A C E \in P

$PSPACE\in P$

# P \in F P

$\#P\in FP$

dapatkah Anda memberikan komentar?

T ....