Direkt zum Inhalt

Lexikon der Mathematik: Entscheidungsproblem

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).

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos