Masalah keputusan adalah salah satu objek utama dari penelitian dalam teori komputasi kompleksitas. Masalah keputusan adalah jenis khusus masalah komputasi yang jawabannya ya atau tidak, atau alternatifnya antara 1 atau 0. Masalah keputusan dapat dilihat sebagai bahasa formal, di mana anggota bahasa adalah contoh yang keluarannya ya, dan non-anggota adalah contoh-contoh yang keluarannya tidak ada. Tujuannya adalah untuk memutuskan, dengan bantuan algoritma, apakah string masukan yang diberikan adalah anggota dari bahasa formal yang sedang dipertimbangkan. Jika algoritma memutuskan masalah ini mengembalikan jawaban ya, algoritma dikatakan menerima string masukan, jika tidak dikatakan menolak masukan.
Apa jenis masalah komputasi yang jawabannya yer atau tidak?
Masalah keputusan