Untuk definisi yang tepat tentang apa artinya menyelesaikan masalah menggunakan jumlah waktu dan ruang yang diberikan, model komputasi seperti mesin Turing deterministik digunakan. Waktu yang dibutuhkan oleh mesin Turing deterministik M pada input x adalah jumlah total transisi keadaan, atau langkah-langkah yang dibuat mesin sebelum berhenti dan mengeluarkan jawaban ("ya" atau "tidak"). Mesin Turing M dikatakan beroperasi dalam waktu f (n), jika waktu yang dibutuhkan oleh M pada setiap input panjang n paling banyak adalah f (n). Masalah keputusan A dapat diselesaikan dalam waktu f (n) jika ada mesin Turing yang beroperasi dalam waktu f (n) yang memecahkan masalah. Karena teori kompleksitas tertarik untuk mengklasifikasikan masalah berdasarkan kesulitannya, orang mendefinisikan serangkaian masalah berdasarkan beberapa kriteria. Sebagai contoh, serangkaian masalah yang dapat diselesaikan dalam waktu f (n) pada mesin Turing deterministik kemudian dilambangkan dengan DTIME (f (n)).
Apa ungkapan yang digunakan untuk mengidentifikasi serangkaian solusi tertentu yang mampu diselesaikan dalam waktu pada mesin Turing deterministik?
DTIME (f (n)).
DTIME (f (n)).
Apa PRI
ungkapan NNO
yang PRR
digunakan VBP
untuk PPO
mengidentifikasi VBT
serangkaian NNO
solusi NNO
tertentu ADJ
yang PRR
mampu VBI
diselesaikan VBP
dalam PPO
waktu NNO
pada PPO
mesin NNO
Turing NNO
deterministik NNP
? PUN