Masalah keputusan adalah salah satu objek utama studi dalam teori kompleksitas komputasi. Masalah keputusan adalah jenis khusus masalah komputasi yang jawabannya adalah ya atau tidak, atau bergantian 1 atau 0. Masalah keputusan dapat dilihat sebagai bahasa formal, di mana anggota bahasa adalah contoh yang keluarannya adalah ya, dan yang bukan anggota adalah contoh-contoh yang outputnya tidak. Tujuannya adalah untuk memutuskan, dengan bantuan algoritma, apakah string input yang diberikan adalah anggota dari bahasa formal yang sedang dipertimbangkan. Jika algoritme yang memutuskan masalah ini mengembalikan jawaban ya, algoritme tersebut dikatakan menerima string input, jika tidak maka dikatakan menolak input.
Apa jenis khas dari masalah komputasi yang jawabannya adalah ya atau tidak?
Masalah keputusan
Masalah keputusan
Apa PRI
jenis NNO
khas ADJ
dari PPO
masalah NNO
komputasi NNO
yang PRR
jawaban NNO
nya PRK
adalah VBL
ya INT
atau CCN
tidak NEG
? PUN