Definition: Ein Entscheidungsproblem ist ein Problem, das nur zwei mögliche Lösungen hat: entweder "ja" oder "nein".
Beispiel: Das Primzahlproblem ist ein Entscheidungsproblem. Das Primzahlproblem besteht darin, für eine beliebige natürliche Zahl m die Frage zu beantworten: "Ist m eine Primzahl?"
Wir verwenden hier den Begriff "Problem" eigentlich für eine ganze Klasse gleichartiger Einzelprobleme. Das Primzahlproblem etwa enthält als Einzelprobleme: "Ist 1 eine Primzahl?", "Ist 2 eine Primzahl?", "Ist 3 eine Primzahl?" usw. Ein solches Einzelproblem nennen wir einen Fall (engl.: instance) des Problems. "Ist 38 eine Primzahl?" ist also ein Fall des Primzahlproblems.
Ein sehr universelles Entscheidungsproblem ist das Wortproblem.
Definition: Sei A ein Alphabet und A* die Menge aller Wörter über A. Sei ferner L ⊆ A* eine Sprache über A. Das Wortproblem besteht darin, für ein beliebiges Wort w ∈ A* folgende Frage zu beantworten: "Ist w ∈ L?"
Sei das Alphabet A vorgegeben. Dann ist das Wortproblem also charakterisiert durch die entsprechende Sprache L, und ein Fall des Wortproblems ist charakterisiert durch ein Paar (w, L).
Durch eine geeignete Codierung lässt sich ein Entscheidungsproblem in ein Wortproblem umwandeln. Beispielsweise kann man die natürlichen Zahlen als Wörter über A = {0, ..., 9} codieren (was man gemeinhin auch tut, indem man sie in Dezimaldarstellung schreibt). Die Primzahlen, ebenfalls in Dezimaldarstellung codiert, bilden dann eine Teilmenge der Menge aller Wörter über A, nämlich die Sprache PRIMES ⊆ A*. Die Frage "Ist die Zahl 789 eine Primzahl?" lässt sich nun umformulieren in "Ist das Wort 789 ein Element der Sprache PRIMES?"
Entscheidungsprobleme lassen sich also zurückführen auf Wortprobleme, und Wortprobleme entsprechen Sprachen. Wir können daher die Begriffe "Entscheidungsproblem" und "Sprache" miteinander identifizieren, wenn wir uns das Entscheidungsproblem als Wortproblem codiert vorstellen. Die Problemgröße eines bestimmten Falles des Wortproblems entspricht dann der Länge des Wortes.
Im Folgenden geht es darum, Entscheidungsprobleme durch Transformation ineinander umzuformen.
Definition: Gegeben seien zwei Sprachen R und S über einem gemeinsamen Alphabet A. Die Sprache R lässt sich in die Sprache S transformieren, wenn es eine berechenbare Abbildung f : A* → A* gibt, derart dass für alle w ∈ A* gilt
w ∈ R ⇔ f(w) ∈ S.
Diese Abbildung f wird dann als Transformation von R nach S bezeichnet.
Wichtig ist, dass die Abbildung f berechenbar ist und dass sie auf ganz A*, also auf der Menge aller Wörter über dem Alphabet A, definiert ist und nicht nur auf R.
Beispiel: Sei A = {0, ..., 9} und sei R diejenige Sprache, die aus den Dezimaldarstellungen aller durch 5 teilbaren nichtnegativen ganzen Zahlen besteht, wobei führende Nullen zugelassen sind, d.h.
R = 0*{0, 5, 10, 15, 20, 25, ... }
Die Abbildung f sei wie folgt definiert. Für alle Wörter w ∈ A* mit w = w0 ... wn-1 sei
f(w) = wn-1
d.h. wir betrachten nur die letzte Ziffer von w.
Die Sprache S sei nun
S = {0, 5}.
Tatsächlich ist f eine Transformation von R nach S, denn es gilt für alle Wörter w ∈ A*
w ∈ R ⇔ f(w) ∈ S,
denn eine beliebige nichtnegative ganze Zahl ist genau dann durch 5 teilbar, wenn ihre letzte Ziffer gleich 0 oder 5 ist.
Ist eine Transformation f einer Sprache R nach einer Sprache S gegeben, so lässt sich das Wortproblem (w, R) lösen, indem w' = f(w) berechnet wird und dann das Wortproblem (w', S) gelöst wird. Man sagt dann, dass sich das Problem R auf das Problem S reduzieren lässt.
Indem also das Problem w' gelöst wird, ist damit auch w gelöst. Haben wir also ein Problemlösungsverfahren für S, haben wir damit auch eines für R, indem wir die Transformation f und das Problemlösungsverfahren für S hintereinander ausführen. Die Prüfung der Teilbarkeit durch 5 ist ein Beispiel hierfür.
Im täglichen Leben versuchen wir meist, schwierige Probleme, die wir nicht lösen können, auf leichtere Probleme, die wir lösen können, zu reduzieren. In Wirklichkeit aber ist es nicht möglich, ein schweres Problem R auf ein leichtes Problem S zu reduzieren, es sei denn, die Schwierigkeit steckt in der Transformation. Denn das Problem R ist ja tatsächlich nicht schwierig, wenn man es leicht in ein leichtes Problem S transformieren und dieses dann lösen kann.
Umgekehrt ist es dagegen möglich, ein leichtes Problem in ein schweres Problem zu transformieren, nach dem Motto: "Warum einfach, wenn's auch kompliziert geht?" Wir kleiden gewissermaßen das leichte Problem so ein, dass es zu einem schwierigen Problem wird. Wenn wir das schwierige Problem dann lösen, fällt die Lösung des leichten Problems dabei ab.
So können wir z.B. feststellen, ob eine Zahl durch 5 teilbar ist (leichtes Problem), indem wir die Zahl in ihre Primfaktoren zerlegen (schweres Problem) und prüfen, ob die 5 unter den Primfaktoren auftritt.
Die Frage ist nun: Wenn es unmöglich ist, schwere auf leichte Probleme zu reduzieren und wenn es unsinnig ist, leichte auf schwere Probleme zu reduzieren, wozu werden dann Reduktionen überhaupt gebraucht? Die Antwort ist: Um zu zeigen, dass ein Problem mindestens so schwer ist wie ein anderes, oder dass es höchstens so schwer ist, oder dass die beiden Probleme im Wesentlichen gleich schwer sind.
Aufgabe 1: Formulieren Sie die Regel für die Teilbarkeit durch 3 als Transformation f von einer Sprache R in eine Sprache S. Geben Sie R, S und f an.
Weiter mit: [Die Mengen