Hubungan kompleksitas algoritma dan kelas automata

Saya tidak dapat menemukan grafik yang menggambarkan atau teks yang menjawab pertanyaan berikut: Apakah ada hubungan langsung antara kompleksitas suatu algoritma (seperti kasus cepat / terbaik terbaik), dan kelas automata yang dapat mengimplementasikan algoritma. Misalnya apakah ada serangkaian kompleksitas yang dapat diekspresikan automata? Jika jawabannya ya untuk pertanyaan itu, adakah sumber yang menggambarkan hubungan itu? Terima kasih!

Ya, ada banyak hubungan dalam banyak kasus!

Sebagai contoh, diketahui bahwa bahasa apa pun yang diterima oleh mesin pencacah pembalikan berada di (lihat di sini ).$P$

Demikian pula, kita tahu bahwa semua bahasa reguler dalam , karena ada algoritma waktu polinomial untuk menentukan apakah NFA menerima kata yang diberikan.$P$

Ada terlalu banyak untuk disebutkan di sini, tetapi secara umum, model komputasi yang lebih terbatas berada di kelas kompleksitas yang lebih mudah.

Berikut adalah beberapa hasil yang diketahui:

1. $\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$ , di mana adalah himpunan bahasa biasa. Untuk bukti, lihat halaman Wikipedia di .$\mathsf{REG}$$\mathsf{DSPACE}$

2. $\mathsf{DCFL} \subseteq \mathsf{SC}$ , di mana adalah sekumpulan bahasa bebas konteks deterministik, dan adalah kelas Steve . Lihat halaman Wikipedia di .$\mathsf{DCFL}$$\mathsf{SC}$$\mathsf{DCFL}$

3. $\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$ , di mana adalah sekumpulan bahasa logspace-dapat direduksi menjadi bahasa bebas konteks. Lihat halaman Wikipedia pada , yang juga memberikan beberapa bahasa lengkap untuk bawah pengurangan ruang log.$\mathsf{LOGCFL}$$\mathsf{LOGCFL}$$\mathsf{LOGCFL}$

4. $\mathsf{CSL} = \mathsf{NSPACE}(n)$ , di mana adalah sekumpulan bahasa yang peka konteks. Lihat halaman Wikipedia di .$\mathsf{CSL}$$\mathsf{CSL}$

5. Kelas bahasa yang diterima oleh determinasi nonerasing PDA adalah , dan kelas bahasa yang diterima oleh PDA nonerasing non-deterministik adalah . Lihat halaman Wikipedia di PDA .$\mathsf{DSPACE(n\log n)}$$\mathsf{NSPACE}(n^2)$

6. Automata dua-stack setara daya untuk mesin Turing, tetapi membatasi hasil automata dalam model yang lebih lemah. Lihat laporan teknis San Pietro.

Apakah ada hubungan langsung antara kompleksitas suatu algoritma (seperti best / worst case of quick sort), dan kelas automata yang dapat mengimplementasikan algoritma.

Pertanyaan yang mana kelas automata dapat mengimplementasikan algoritma yang diberikan seperti quick sort itu rumit, karena tidak jelas apa yang akan dihitung sebagai implementasi dari algoritma itu. Untuk penyortiran cepat, perbandingan yang dilakukan tentu harus sama, tetapi haruskah urutan di mana perbandingan terjadi juga sama? Bagaimana dengan urutan akses baca ke elemen input tertentu? Urutan menyalin, memindahkan, dan menukar operasi untuk elemen tertentu?

Anda harus menentukan cukup banyak nubuat untuk operasi yang penting bagi Anda, tetapi kemudian Anda sudah berada dalam situasi yang sangat spesifik berdasarkan algoritma, dan cukup jauh dari kelas umum automata yang biasanya dipelajari. Cara mengatasi dilema ini adalah dengan membicarakan masalah alih-alih algoritma, dan meresmikan masalah dengan berbicara tentang bahasa.

Misalnya apakah ada serangkaian kompleksitas yang dapat diekspresikan automata?

Tidak juga, karena push down automata dapat membaca inputnya hanya sekali dan hanya di arah maju. Namun, jika Anda membagi mesin menjadi bagian yang diizinkan untuk membaca input maju dan mundur sesuai keinginan, dan mempertahankan sejumlah terbatas pointer ke posisi input tertentu (NL), dan bagian yang merupakan automata push down yang menerima inputnya dari bagian lain, maka Anda mendapatkan kelas kompleksitas LOGCFL , yang sama dengan SAC ¹ (kelas sirkuit).

Jika Anda tidak memisahkan dua bagian dan hanya menambahkan stack untuk NL, maka Anda mendapatkan kelas automata AuxPDA , yang sama dengan kelas kompleksitas P . Tetapi jika Anda memutuskan untuk membatasi runtime automata itu (dengan penyimpanan tambahan stack dan logaritmik) ke waktu polinomial, maka Anda mendapatkan NAuxPDA ^P , yang lagi-lagi sama dengan LOGCFL. (Dan jika Anda bersikeras runtime polinomial deterministik, memo tumpukan, tetapi memungkinkan penyimpanan tambahan polylogarithmic, maka Anda mendapatkan SC .)

Di sisi lain, jika Anda mempertahankan batasan bahwa automata dapat membaca inputnya hanya sekali dan hanya dalam arah maju, dan juga mensyaratkan bahwa ia dapat menggunakan stack-nya hanya dengan cara yang sangat deterministik langsung berdasarkan input (yaitu simbol input menentukan apakah automata mendorong sesuatu pada stack, mengeluarkan sesuatu dari stack, atau membiarkan stack tidak tersentuh), kemudian Anda berakhir dengan automata yang terlihat jelas, yang mengenali persis kata-kata kata bersarang , yang juga dapat dikenali dalam ruang logaritmik deterministik, yang juga dapat dikenali dalam ruang logaritmik deterministik. .