Namun, beberapa masalah komputasi lebih mudah untuk dianalisis dalam hal sumber daya yang lebih tidak biasa. Misalnya, mesin Turing non-deterministik adalah model komputasi yang diizinkan untuk bercabang untuk memeriksa berbagai kemungkinan sekaligus. Mesin Turing non-deterministik sangat sedikit hubungannya dengan bagaimana kita secara fisik ingin menghitung algoritma, tetapi percabangannya menangkap dengan tepat banyak model matematika yang ingin kita analisis, sehingga waktu non-deterministik adalah sumber daya yang sangat penting dalam menganalisis masalah komputasi .
Apa jenis mesin Turing yang dapat dikarakterisasi dengan memeriksa beberapa kemungkinan pada saat yang bersamaan?
non-deterministik
non-deterministik
Apa PRI
jenis NNO
mesin NNO
Turing NNO
yang PRR
dapat TAME
dikarakterisasi VBP
dengan PPO
memeriksa VBT
beberapa KUA
kemungkinan NNO
pada PPO
saat NNO
yang PRR
bersamaan VBI
? PUN