Masalah apa pun yang dipecahkan oleh robot terbatas ada di P

Setelah kelas Teori Komputasi saya hari ini, pertanyaan ini muncul di benak saya: Jika masalah dapat diselesaikan oleh robot terbatas, masalah ini milik P.

Saya pikir itu benar, karena automata mengenali bahasa yang sangat sederhana, maka semua bahasa ini akan memiliki algoritma polinomial untuk menyelesaikannya. Jadi, apakah benar bahwa masalah yang diselesaikan oleh otomat terbatas ada di P?

Ya itu benar. Dalam hal kelas kompleksitas,

$$\text{REG} \subseteq \text{P},$$ dimana $\text{REG}$adalah kelas bahasa reguler (yaitu, masalah yang dapat dipecahkan oleh robot terbatas). Lebih spesifik, $$\text{REG} \subseteq \text{DTIME}(n), \tag{*}$$ dan $\text{DTIME}(n)$ adalah bagian ketat dari $\text{P}$ oleh teorema hierarki waktu.

Bukti (*) adalah sebagai berikut: untuk masalah apa pun di $\text{REG}$, ada DFA yang menyelesaikannya. Ubah DFA menjadi mesin Turing dengan status dan fungsi transisi yang sama, yang selalu bergerak ke kanan hingga terlihat kosong, lalu menerima atau menolak. Mesin Turing ini selalu berhenti tepat waktu$n$.

---

Perlu juga disebutkan

$$\text{REG} = \text{DSPACE}(0) = \text{DSPACE}(k)$$ untuk konstanta tetap $k$.

Ya ini benar. Untuk setiap masalah seperti itu ada DFA yang memutuskan bahasa, dan memeriksa apakah sebuah kata diterima oleh DFA dapat dengan mudah dilakukan dalam waktu linier dalam panjang kata.