Perhitungan Deterministik vs. Nondeterministik
Untuk memahami kelas P dan NP, pertama-tama kita harus mengetahui model komputasi. Karenanya, dalam bab ini kita akan membahas dua model komputasi penting.
Perhitungan Determinan dan Kelas P
Mesin Turing Determinan
Salah satu model ini adalah mesin Turing satu pita deterministik. Mesin ini terdiri dari kontrol keadaan hingga, kepala baca-tulis, dan pita dua arah dengan urutan tak terbatas.
Berikut adalah diagram skema dari mesin Turing satu pita deterministik.
Program untuk mesin Turing deterministik menetapkan informasi berikut -
- Satu set simbol pita terbatas (simbol input dan simbol kosong)
- Sekumpulan negara yang terbatas
- Fungsi transisi
Dalam analisis algoritmik, jika suatu masalah dapat dipecahkan dalam waktu polinomial oleh mesin Turing satu pita deterministik, masalah tersebut termasuk dalam kelas P.
Perhitungan Nondeterministik dan Kelas NP
Mesin Turing Nondeterministic
Untuk mengatasi masalah komputasi, model lain adalah Non-deterministic Turing Machine (NDTM). Struktur NDTM mirip dengan DTM, namun di sini kami memiliki satu modul tambahan yang disebut modul menebak, yang dikaitkan dengan satu kepala tulis saja.
Berikut diagram skematiknya.
Jika masalah dapat diselesaikan dalam waktu polinomial oleh mesin Turing non-deterministik, masalah tersebut termasuk dalam kelas NP.