Entscheidungsproblem

Als Entscheidungsproblem bezeichnet man in der Informatik Probleme, für die zu einer gegebenen Eingabe als Lösung nur zwei Antworten (z.B. ja oder nein bzw. 0 oder 1 usw.) vorgesehen sind. Jedes Entscheidungsproblem läßt sich als das Wortproblem einer formalen Sprache auffassen.

siehe auch: Optimierungsproblem, Suchproblem