ANALISIS KELAS KOMPLEKSITAS BERDASARKAN BERBAGAI JENIS MESIN TURING DALAM TEORI KOMPUTASI

Abstract

Di dalam teori komputasi, banyak jenis mesin Turing digunakan untuk menentukan kelas kompleksitas, seperti mesin Turing deterministik, mesin Turing probabilistik, mesin Turing non-deterministik, mesin Turing kuantum, mesin Turing simetris dan mesin Turing bolak-balik. Semuanya sama-sama kuat pada prinsipnya, namun bila sumber daya (seperti waktu atau ruang) dibatasi, beberapa di antaranya mungkin lebih kuat daripada yang lain. Mesin Turing deterministik adalah mesin Turing yang paling dasar, yang menggunakan seperangkat aturan tetap untuk menentukan tindakan masa depannya. Mesin Turing probabilistik adalah mesin Turing deterministik dengan persediaan bit acak tambahan. Kemampuan untuk membuat keputusan probabilistik sering membantu algoritma memecahkan masalah dengan lebih efisien. Algoritma yang menggunakan random bits disebut algoritma acak. Mesin Turing non-deterministik adalah mesin Turing deterministik dengan fitur tambahan non-determinisme, yang memungkinkan mesin Turing memiliki banyak kemungkinan tindakan di masa depan dari keadaan tertentu. Artikel ini menjabarkan kelas-kelas kompleksitas penting yang didefinisikan dengan membatasi waktu (Time Complexity Class) atau ruang (Space Complexity Class) yang digunakan oleh algoritma, serta kelas kompleksitas dari algoritma acak yang disebut (Randomized Complexity Class).