ein Problem, bei dem als Ergebnisse nur „ja“ bzw. 1 und „nein“ bzw. 0 möglich sind.

Es muß entschieden werden, ob die Eingabe akzeptiert oder verworfen wird. Entscheidungsprobleme werden auch als Sprachen bezeichnet.

Optimierungsprobleme haben Entscheidungsvarianten, bei denen entschieden werden muß, ob der optimale Wert einer Lösung des Optimierungsproblems für eine Schranke s, die zur Eingabe gehört, bei Maximierungsproblemen mindestens und bei Minimierungsproblemen höchstens den Wert s hat.

Algorithmen für Optimierungsprobleme lösen auch die Entscheidungsvarianten. Für viele Probleme, z. B. Cliquenproblem, Rucksackproblem und TSP (Traveling-Salesman-Problem), gilt, daß es eine Turing-Reduktion von dem Optimierungsproblem auf die Entscheidungsvariante gibt. Aus Sicht der Komplexitätstheorie genügt es dann, die Entscheidungsvarianten zu untersuchen (Entscheidungstheorie).