Turingreduktion

Die Reduktion ist eine Methode der Theoretischen Informatik. Eine Reduktion ist die Lösung eines Problems mit Hilfe eines hypothetischen Algorithmus für ein anderes Problem. Die Reduzierbarkeit ist somit eine Relation zwischen zwei Problemen. Durch sie können die Berechenbarkeit oder die Komplexität von Problemen zueinander in Bezug gesetzt werden.

Man unterscheidet verschiedene Typen von Reduktionen. Bei einer nicht weiter spezifizierten Reduktion ist meist die many-one-Reduktion gemeint; weitere wichtige Varianten sind one-one-Reduktion und tt-Reduktion (von engl. truth table, Wahrheitstabelle). Alle sind Sonderfälle der Turingreduktion.

In der Berechenbarkeitstheorie genügt in der Regel der Nachweis der Anwendbarkeit beziehungsweise Nichtanwendbarkeit einer Reduktion. Dagegen werden in der Komplexitätstheorie zusätzliche Anforderungen an Reduktionen gestellt, wie etwa die logarithmisch platzbeschränkte Reduktion. Hierbei wird gefordert, dass die Reduktion innerhalb einer bestimmten Komplexitätsschranke durchgeführt werden kann. Eine andere Form solcher beschränkten Reduktionen sind die FO-Reduktionen der deskriptiven Komplexitätstheorie.

Ein erweitertes Reduktionskonzept ist für Approximationsalgorithmen notwendig, die PTAS-Reduktion.

Typen von Reduktionen

Die allgemeinste Form der Reduktion ist die Turingreduktion. Hier darf der vorausgesetzte Algorithmus beliebig oft aufgerufen werden um das betrachtete Problem zu lösen. Jeder Aufruf wird dabei als einzelner Rechenschritt gewertet. Zur formalen Definition dieser Reduktion wird die Orakel-Turingmaschine verwendet.

Die Turingreduktion ist eine sehr mächtige Form der Reduktion. Dies macht es einerseits einfach, Reduktionen zu entwerfen, bringt aber andererseits auch Probleme mit sich. Insbesondere ist es durch Turingreduktion nicht möglich, zwischen einem Problem und seinem Komplement zu unterscheiden. Aus diesem Grund ist zum Beispiel nicht bekannt, ob die Komplexitätsklasse NP unter Polynomialzeit-Turingreduktion abgeschlossen ist.

Es werden daher eingeschränkte Reduktionsvarianten verwendet. Bei many-one-Reduktionen darf der Algorithmus für das Problem, auf das reduziert wird, nur ein einziges Mal aufgerufen werden. Das Ergebnis muss anschließend ohne weitere Bearbeitung ausgegeben werden. Durch diese zweite Bedingung kann zwischen einem Entscheidungsproblem und seinem Komplement unterschieden werden. Die many-one-Reduktion entspricht einer Umformung von einem Problem in ein anderes Problem.

Definitionen

Formal werden für die Relation „A ist reduzierbar auf B“ die Schreibweisen $A\preceq B$ oder $A\leq B$ verwendet. Oft werden dabei tiefgestellt der Typ der Reduktion und hochgestellt eine Komplexitätsschranke angegeben, beispielsweise $A\preceq_m^p B$ für „A ist polynomiell many-one-reduzierbar auf B“.

Turingreduktion

Ein Problem A ist turingreduzierbar auf ein Problem B, $A\preceq_T B$, wenn es eine Orakel-Turingmaschine mit Orakel B gibt, welche A berechnet.

Many-one-Reduktion und one-one-Reduktion

Eine Formale Sprache L' ist auf eine Sprache L many-one-reduzierbar, $L'\preceq_m L$, wenn eine totale, berechenbare Funktion $f: \Sigma^* \longrightarrow \Sigma^*$ auf der Menge aller Eingabewörter Σ^* existiert, so dass gilt: $w \in L'$ genau dann, wenn $f(w) \in L$.

Wenn $L'\preceq_m L$ gilt und es außerdem eine injektive Reduktionsfunktion f gibt, heißt L' one-one-reduzierbar auf L, $L'\preceq_{1}L$.

Beispiele

Ein positives Beispiel

Die Sprache aller Quadratzahlen

$L_Q := \left\{ (a,b) \colon b = a^2, a \in \Z\right\}$

lässt sich auf die Sprache aller Multiplikationen mit 2 Faktoren

$L_M := \left\{ (a_1, a_2,b) \in \Z^3\colon b = a_1 \cdot a_2\right\}$

reduzieren, da über die Abbildung $f\colon \Z^2 \to \Z^3, \, (a,b) \mapsto (a,a,b)$ jedes Wort aus L_Q in ein Wort aus L_M abgebildet werden kann und jedes Bild dieser Funktion $f\;$ wiederum ein Urbild in L_Q besitzt.

Mit dieser Reduktion ist gezeigt, dass ein Algorithmus, welcher zwei natürliche Zahlen miteinander multipliziert, auch eine natürliche Zahl quadrieren kann, das Quadrieren kann also auf das Multiplizieren reduziert werden.

Ein negatives Beispiel

Das Halteproblem ist nicht auf sein Komplement many-one-reduzierbar, denn es ist nur rekursiv aufzählbar, aber nicht entscheidbar.

Reduktionen in der Komplexitätstheorie

In der Komplexitätstheorie möchte man nicht nur qualitativ wissen, ob eine Reduktion existiert, sondern auch quantitativ den Aufwand zueinander in Bezug setzen. So will man ausdrücken: „Eine Sprache ist auf eine andere komplexitätstheoretisch reduzierbar genau dann, wenn die eine nicht schwerer ist als die andere.“ Hierfür müssen an die Reduktionsfunktion f zusätzliche Anforderungen gestellt werden:

• Ist f in polynomieller Zeit berechenbar, so ist f eine Polynomialzeitreduktion.
• Ist f auf logarithmischem Platz berechenbar, so ist f eine logarithmisch platzbeschränkte Reduktion.

Solcherart beschränkte Reduktionen sind die Basis der Vollständigkeit, einem wichtigen Werkzeug der Komplexitätstheorie. Ein Problem ist vollständig für eine Komplexitätsklasse, wenn jedes andere Problem der Klasse darauf reduziert werden kann.

Diese Eigenschaft kann auch zur Definition einer Komplexitätsklasse herangezogen werden, indem zunächst ein vollständiges Problem der Klasse festgelegt wird. Beispielsweise kann die Klasse NP als Reduktionsklasse verstanden werden, nämlich als die Klasse aller Probleme, die logarithmisch platzbeschränkt (oder auch polynomiell zeitbeschränkt) auf das Erfüllbarkeitsproblem der Aussagenlogik many-one-reduzierbar sind.

Literatur

• Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967. Nachdruck bei MIT-Press Cambridge (Massachusetts), London (England), 1987.
• Ingo Wegener: Theoretische Informatik - eine algorithmische Einführung. 3. Auflage, Sept. 2005
• Katrin Erk, Lutz Priese: Theoretische Informatik. 2. Auflage, Aug. 2001
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman: Einführung in die Automatentheorie, Formale Sprachen und Komplexitätstheorie. 2. Auflage, 2002