Kelas kompleksitas sesuai dengan penyortiran

Dua bagian TCS adalah algoritma dan kompleksitas. Saya secara sederhana akan mengatakan bahwa algoritma adalah studi tentang batas atas, menunjukkan bahwa Anda dapat melakukan sesuatu (dengan sumber daya yang diberikan terbatas), dan kompleksitas adalah tentang menunjukkan bahwa Anda tidak dapat melakukannya tanpa sumber daya minimal.

Begitu sering masalah algoritmik dinyatakan dalam model keputusan untuk menempatkannya dalam kelas kompleksitas.

Tetapi sesuatu yang selalu mengganggu saya adalah bahwa beberapa algoritma elementer tidak pernah disebut sebagai milik kelas tertentu. Salah satu contoh adalah penyortiran (perbandingan). Cobalah sekuat tenaga, kelas yang relevan sepertinya terlalu kurang (sungguh, apakah hanya memeriksa di logspace bahwa hasilnya diurutkan? Kelihatannya terlalu lemah, atau saya tidak mendapatkan versi keputusan dengan benar).

Apa kelas kompleksitas terbaik / paling tepat / paling berguna yang berada dalam penyortiran perbandingan?

cc.complexity-theory sorting Mitch
sumber

Jawaban:

Masalah penyortiran sebenarnya lengkap untuk $\mathsf{TC}^0$ (di bawah -reduction). Sumber standar untuk ini adalah Bagian 1.4.3 dari buku Vollmer . $\mathsf{AC}^0$

Perhatikan bahwa adalah kelas masalah keputusan, tetapi kami biasanya menganggap pengurutan sebagai masalah fungsi, yaitu, kami ingin menampilkan angka-angka, katakanlah, dalam urutan nondecreasing. Namun, kami juga dapat mendefinisikan penyortiran sebagai masalah keputusan sebagai berikut: $\mathsf{TC}^0$

Mengingat urutan angka dan dua nomor , kita ingin memutuskan apakah adalah pada posisi di urutan kita mendapatkan dengan menyortir di nondecreasing memesan. Perhatikan bahwa untuk menghindari ambiguitas, ketika , kami ingin $a_1,\ldots,a_n$ $k,p\in [n]$ $a_k$ $p$ $a_1,\ldots,a_n$ $a_i=a_j$ mendahului jika . $a_i$ $a_j$ $i<j$

Dai Le
sumber

Luar biasa ... ditentukan sebagai masalah keputusan formal apa?

Mitch

Akan sangat baik untuk memasukkan referensi dalam jawaban Anda.

Oleksandr Bondarenko

@Mitch dan @Okeksandr: Terima kasih atas komentar Anda! Saya baru saja memperluas jawaban saya untuk memperjelas poin-poin itu.

Dai Le

Itu terdengar seperti masalah keputusan untuk statistik pesanan. Apakah ada masalah terkait di mana semuanya ada di tempat yang benar? Sesuatu seperti diberi urutan

dan permutasi

pada

, memutuskan apakah

. Ini sesulit milikmu; Apakah lebih sulit atau lengkap untuk kelas yang disertakan?

a_{1} . . . a_{n}

$a_1...a_n$

σ

$\sigma$

[1.. n]

$[1..n]$

\forall_{1 \leq k < j \leq n}, a_{σ_{k}} < a_{σ_{j}}

$\forall_{1\le k\lt j\le n}, a_{\sigma_k} < a_{\sigma_j}$

Mitch

@Itch: Saya percaya bahwa memeriksa apakah semuanya ada di tempat yang tepat seperti itu sebenarnya lebih mudah daripada menyortir. Intuisi adalah bahwa Anda dapat memeriksa bahwa

untuk semua pasangan yang mungkin

dengan

secara paralel, yang saya percaya dapat dilakukan dalam

. Untuk masalah penyortiran di atas, Anda harus dapat "menghitung" untuk mengetahui posisi yang tepat dari angka dalam urutan linear.

a_{σ_{k}} < a_{σ_{j}}

$a_{\sigma_k}<a_{\sigma_j}$

(a_{σ_{k}}, a_{σ_{j}})

$(a_{\sigma_k},a_{\sigma_j})$

k < j

$k<j$

{A C}^{0}

$\mathsf{AC}^0$

Dai Le

Saya percaya FP adalah apa yang Anda cari.

Nicholas Mancuso
sumber

Yah, saya lebih mencari kelas kompleksitas keputusan yang relevan daripada yang fungsional, tetapi meskipun demikian, saya cukup yakin bahwa penyortiran perbandingan tidak ada di dekat P-complete (atau FP-complete), jadi saya berharap kelas yang lebih kecil yang diharapkan / selesai untuk.

Mitch

Saya tidak menyadari bahwa kelengkapan adalah salah satu syarat untuk pertanyaan Anda. Sebagai masalah keputusan (jika Anda mengabaikan kendala kelengkapan Anda) mengapa P tidak dapat diterima sebagai jawaban? Diberikan DTM Anda dapat menghasilkan dan memvalidasi sertifikat dalam waktu polinomial.

Nicholas Mancuso

Diberikan masalah umum, apa yang biasanya ingin saya ketahui bukan hanya itu waktu polinomial, tetapi kelas terkecil yang bisa masuk. Saya ingin tahu apakah itu dalam LOGCFL, NL, L, AC_0, dll. Kelengkapan adalah salah satu cara Anda "tidak bisa" melakukan yang lebih baik. Jadi nit bukan persyaratan pertanyaan saya, tetapi kemungkinan hal yang ada dalam jawaban.

Mitch