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

  • Die Autoren
- Prof. Dr. Guido Walz

Schreiben Sie uns!

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.

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.