Mengapa kita menganggap ruang log sebagai model perhitungan yang efisien (bukan ruang polylog)?

Ini mungkin pertanyaan subyektif dan bukan pertanyaan jawaban yang konkret.

Dalam teori kompleksitas kita mempelajari pengertian perhitungan yang efisien. Ada kelas-kelas seperti singkatan untuk waktu polinomial , dan L berarti ruang log . Keduanya dianggap direpresentasikan sebagai semacam "efisiensi", dan mereka menangkap kesulitan dari beberapa masalah dengan cukup baik.$\mathsf{P}$$\mathsf{L}$

Tapi ada perbedaan antara dan L : sementara waktu polinomial, P , didefinisikan sebagai penyatuan masalah yang berjalan di O ( n k ) waktu untuk setiap konstanta k , yaitu,$\mathsf{P}$$\mathsf{L}$$\mathsf{P}$$O(n^k)$$k$

,$\mathsf{P} = \bigcup_{k \geq 0} \mathsf{TIME[n^k]}$

ruang log, , didefinisikan sebagai S P A C E [ log n ] . Jika kita meniru definisi P , itu menjadi$\mathsf{L}$$\mathsf{SPACE[\log n]}$$\mathsf{P}$

,$\mathsf{PolyL} = \bigcup_{k \geq 0} \mathsf{SPACE[\log^k n]}$

di mana disebut kelas ruang polylog . Pertanyaanku adalah:$\mathsf{PolyL}$

Mengapa kita menggunakan ruang log sebagai gagasan perhitungan efisien, bukan ruang polylog?

Satu masalah utama mungkin tentang set masalah lengkap. Di bawah reduksi banyak-satu logspace, dan L memiliki masalah lengkap. Sebaliknya, jika P o l y L memiliki masalah lengkap di bawah pengurangan tersebut, maka kita akan bertentangan dengan teorema hierarki ruang. Tetapi bagaimana jika kita pindah ke reduksi polylog? Bisakah kita menghindari masalah seperti itu? Secara umum, jika kita mencoba yang terbaik untuk menyesuaikan P o l y L ke dalam konsep efisiensi, dan (jika perlu) memodifikasi beberapa definisi untuk mendapatkan setiap properti yang baik, kelas "bagus" seharusnya, sejauh mana kita bisa melangkah?$\mathsf{P}$$\mathsf{L}$$\mathsf{PolyL}$$\mathsf{PolyL}$

Apakah ada alasan teoretis dan / atau praktis untuk menggunakan ruang log alih-alih ruang polylog?

Kelas terkecil yang mengandung waktu linier dan ditutup di bawah subrutin adalah P. Kelas terkecil yang berisi ruang log dan ditutup di bawah subrutin masih ruang log. Jadi P dan L adalah kelas kuat terkecil untuk waktu dan ruang masing-masing yang mengapa mereka merasa tepat untuk memodelkan perhitungan yang efisien.

$\text{SPACE}[\log^2 n] \subseteq \text{P}$$\log^{k-1}(n)$$\text{NSPACE}$$[\log^k n]$$\text{-complete}$

$\text{PLOSS} = \bigcup_k \text{TISP}[n^k, k \, \log^2 n]$$\text{DCFL} \subseteq \text{PLOSS}$$\text{SC}^2$$\text{SC}^k$

$2^{O(\log n)} = \operatorname{poly}(n)$

$\text{NSPACE}[\log^k n] \subseteq \text{SPACE}[\log^{2k}n]$

$\text{SC}^k = \text{TISP}[\operatorname{poly}(n), \log^k n]$

Saya pikir semua jawaban lain sangat bagus; Saya akan mencoba memberikan perspektif yang berbeda tentang masalah ini.

Saya tidak tahu seberapa baik model P perhitungan "efisien" di dunia nyata, tapi kami menyukai kelas karena sifat penutupan yang bagus dan alasan matematika lainnya. Demikian pula, L juga kelas yang bagus karena beberapa alasan yang disebutkan di atas.

Namun, seperti yang Anda komentari, jika kita melonggarkan definisi kita tentang "efisien" hingga waktu polinomial, maka PolyL juga efisien. Kita dapat mendiskusikan teori kompleksitas di mana kita mengizinkan kelas yang didefinisikan dengan ikatan logaritmik pada beberapa sumber daya untuk menggunakan sumber daya polylog sebagai gantinya. Sejalan dengan itu, kami juga akan melonggarkan definisi kami tentang NC, NL, dll. Untuk memungkinkan sirkuit ukuran kuasi polinomial. Jika kita melakukan ini, NC ₁ , L, NL dan NC semuanya bertepatan dengan kelas PolyL. Dalam hal ini PolyL adalah kelas yang kuat karena banyak kelas alami bertepatan dengan itu. Untuk informasi lebih lanjut tentang teori kompleksitas dengan log -> polylog dan polinomial -> quasi-polinomial, lihat kelas sirkuit ukuran Quasipolynomial oleh Barrington.

Alasan lain untuk mempelajari polyL atau kelas serupa seperti quasi-AC ₀ adalah bahwa sementara pemisahan oracle antara (katakanlah) ParityP dan PH menyiratkan bahwa PARITY tidak terkandung dalam AC ₀ , implikasi sebaliknya tidak diketahui benar. Di sisi lain, PARITY tidak terkandung dalam quasi-AC ₀ jika dan hanya jika ada pemisahan oracle antara ParityP dan PH. Demikian pula, kelas quasi-TC ₀ dan quasi-AC ₀ berbeda jika dan hanya jika ada pemisahan oracle antara CH dan PH. Jadi kelas kompleksitas biasa seperti PH, ModPH, CH, dll. Ketika diperkecil oleh eksponensial untuk membuktikan hasil oracle berubah menjadi versi kuasi-polinomial dari kelas biasa AC ₀ , ACC ₀ dan TC₀ masing-masing. Demikian pula, argumen yang digunakan dalam teorema Toda (PH yang terkandung dalam P ^PP ) dapat digunakan untuk menunjukkan bahwa quasi-AC ₀ terkandung dalam kedalaman-3 quasi-TC ₀ . (Saya tidak tahu apakah kesimpulan yang sama diketahui untuk versi biasa dari kelas-kelas ini. Saya telah melihat ini terdaftar sebagai masalah terbuka di beberapa makalah.)