Entscheidungsproblem

Entscheidbar ist eine Eigenschaft dann, wenn es ein Entscheidungsverfahren gibt, für jedes Objekt festzustellen, ob es diese Eigenschaft hat oder nicht. Als Entscheidungsproblem bezeichnet man die Frage, ob und wie für eine gegebene Eigenschaft ein Entscheidungsverfahren formuliert werden kann.

Das Entscheidungsproblem in der Mathematik und Logik

Allgemeines

Das Entscheidungsproblem ist „das Problem, die Allgemeingültigkeit von Ausdrücken festzustellen“ . „Es handelt sich um das Problem, zu einer gegebenen deduktiven Theorie ein allgemeines Verfahren anzugeben, das uns die Entscheidung darüber gestattet, ob ein vorgegebener, in den Begriffen der Theorie formulierter Satz, innerhalb der Theorie bewiesen werden kann oder nicht.“

Entscheidend ist dabei, ob es ein rein mechanisch anzuwendendes Verfahren, einen Algorithmus, gibt, das in endlich vielen Schritten klärt, ob ein Ausdruck, eine Formel, in einem System gültig ist oder nicht.

Nach Frege/Whitehead/Russell war die „Kernfrage der Logiker und Mathematiker: Gibt es einen Algorithmus ..., der von einer beliebigen Formel eines logischen Kalküls feststellt, ob sie aus gewissen vorgegebenen Axiomen folgt oder nicht (das so genannte Entscheidungsproblem) ?“

Das Entscheidungsproblem in einzelnen Logikbereichen

Das Entscheidungsproblem in der Aussagenlogik

Im Aussagenkalkül ist das Entscheidungsproblem gelöst. Ein Entscheidungsverfahren ist in der Aussagenlogik die Methode der Wahrheitstafeln.

Das Entscheidungsproblem in der Prädikatenlogik

Das (spezielle) Entscheidungsproblem für die Prädikatenlogik wurde 1928 von David Hilbert gestellt (siehe Hilbertprogramm). Alan Turing und Alonzo Church haben für das Problem 1936 festgestellt, dass es unlösbar ist (siehe Halteproblem).

Das Entscheidungsproblem ist nicht für die allgemeine Prädikatenlogik, sondern lediglich für einen Teilbereich der Prädikatenlogik, nämlich für die Prädikatenlogik "mit einstelligen Prädikaten 1. Stufe“ gelöst.

Literatur

• Czayka, Logik (1991), S. 45 ff.
• Ausführlich Quine, Grundzüge, 8. Aufl. (1993), S. 142 ff.
• Hoyningen-Huene, Logik (1998), S. 226 ff.

Das Entscheidungsproblem in der Theoretischen Informatik

Allgemeines

Struktur eines Entscheidungsproblems

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

Eine formale Sprache $\mathbf {\mathit {\,S\,}}$ ist entscheidbar (rekursiv entscheidbar), wenn ihre charakteristische Funktion berechenbar ist. Es gibt dann also eine berechenbare Funktion $\mathbf {\mathit {\,f\,}}$, sodass für alle Wörter $\mathbf {\mathit {\,w\,}}$ über die Symbole der Sprache $\mathbf {\mathit {\,S\,}}$ gilt:

$f(w)={\begin{cases}1,&{\textrm {wenn~}}w\in S\\0,&{\textrm {wenn~}}w\notin S\end{cases}}$

Die Semi-Entscheidbarkeit (Rekursive Aufzählbarkeit) einer (formalen) Sprache $\mathbf {\mathit {\,S\,}}$ ist dadurch gekennzeichnet, dass ihre partielle (eingeschränkte) charakteristische Funktion berechenbar ist. Es gibt dann folglich eine berechenbare Funktion $\mathbf {\mathit {\,f^{0}\,}}$, sodass für alle Wörter $\mathbf {\mathit {\,w\,}}$ über die Symbole der Sprache $\mathbf {\mathit {\,S\,}}$ gilt:

$f^{0}(w)={\begin{cases}1,&{\textrm {wenn~}}w\in S\\{\textrm {undefiniert}},&{\textrm {wenn~}}w\notin S\end{cases}}$

Optimierungsprobleme und zugehörige Entscheidungsprobleme

Häufig möchte man in der Komplexitätstheorie die Komplexität von Optimierungs- bzw. Suchproblemen untersuchen. In vielen Fällen ist es jedoch einfacher, das zum Optimierungsproblem zugehörige Entscheidungsproblem zu untersuchen und daraus Rückschlüsse auf das Optimerungsproblem zu ziehen. Das zugehörige Entscheidungsproblem bildet man, indem man nicht mehr nach einer optimalen Lösung fragt, sondern ob zu einem zusätzlich gegebenen k eine Lösung existiert, die mindestens (im Falle von Maximierungsproblemen) bzw. höchstens (im Falle von Minimierungsproblemen) den Lösungswert k besitzt.

Häufig kann man dann zeigen, dass aus der Existenz eines polynomiellen Algorithmus für das Entscheidungsproblem auch die Existenz eines solchen für das Optimierungs- bzw. Suchproblem folgt. Die Umkehrung gilt sowieso. Stellt man außerdem fest, dass das Entscheidungsproblem NP-vollständig ist, so sagt man, dass das Optimierungs- bzw. Suchproblem NP-äquivalent ist.

Siehe auch

• Berechenbarkeit
• Äquivalenzproblem
• Endlichkeitsproblem
• Kreativproblem
• Leerheitsproblem
• Optimierungsproblem
• Suchproblem
• Turingmaschine
• Akzeptieren