Kompleksitas penyortiran

Tidak sulit untuk menunjukkan bahwa mengurutkan array angka sulit untuk . Jika input adalah array dari 1s dan 0s maka pada dasarnya fungsi (diberikan bit, output jumlah 1s dalam biner) karena lengkap untuk dan dimungkinkan untuk mengkonversi angka unary ke angka biner dan (logaritmik) angka biner kecil ke angka unary di : C o u n t n C o u n t T C 0 A C $\mathsf{TC^0}$$Count$$n$$Count$$\mathsf{TC^0}$$\mathsf{AC^0}$

$Count(\vec{x}) = Binary(Sort(\vec{x}))$
$Sort(\vec{x}) = Unary(Count(\vec{x}))$

Jadi kekuatan pada dasarnya menyortir string biner (mis. 100011 hingga 000111). Ini berlaku lebih umum ketika angka-angka dalam array dibatasi. Pertanyaan saya adalah bagaimana jika jumlahnya tidak dibatasi?$\mathsf{TC^0}$

Apakah masalah pengurutan array nomor tidak terikat masih di ? Apakah lengkap untuk kelas yang lebih besar seperti ?$\mathsf{TC^0}$$\mathsf{NC^1}$

Misalkan Anda memiliki angka x 1 , … , x n lebar m ≥ log n . Tanpa kehilangan keumuman, semua angka berbeda (tambahkan log ekstra dan bit urutan lebih rendah). Dua angka dapat dibandingkan dalam AC ⁰ , jadi dalam AC ⁰ kita dapat menghitung, untuk setiap x i , vektor biner v , yang didefinisikan oleh v j = 1 jika x j ≥ x i . Di TC ⁰ kita bisa mengurutkan v ke$n$$x_1,\ldots,x_n$$m \geq \log n$$\log n$$x_i$$v$$v_j = 1$$x_j \geq x_i$$v$ , dan kemudian cari (di AC⁰) posisi k sehingga w k = 1 sedangkan w k - 1 = 0 (di mana w 0 = 0 , w n + 1 = 1 ). Dengan nilai-nilai ini k untuk setiap i ∈ [ n ] , kita dapat menghitung array yang diurutkan dalam AC⁰. Secara total, kami mendapatkansirkuitTC⁰.$w$$k$$w_k = 1$$w_{k-1} = 0$$w_0=0$$w_{n+1}=1$$k$$i \in [n]$