Reduktion (Theoretische Informatik)

Reduktion (Theoretische Informatik)

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.

Inhaltsverzeichnis

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 LQ in ein Wort aus LM abgebildet werden kann und jedes Bild dieser Funktion f\; wiederum ein Urbild in LQ 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:

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 es selbst dieser Klasse angehört und 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

  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung. 2. erweiterte Auflage. Springer, Berlin u. a. 2002, ISBN 3-540-42624-8 (Springer-Lehrbuch).
  • John E. Hopcroft, Rajeev Motwani, Jeffrey Ullman: Einführung in die Automatentheorie, formale Sprachen und Komplexitätstheorie. 2., überarb. Auflage. Pearson Studium, München 2002, ISBN 3-8273-7020-5. 
  • Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York NY u. a. 1967 (McGraw-Hill Series in Higher Mathematics), (Nachdruck. MIT-Press, Cambridge MA u. a. 1987, ISBN 0-262-68052-1).
  • Ingo Wegener: Theoretische Informatik. Eine algorithmische Einführung. 3. überarbeitete Auflage. Teubner, Wiesbaden 2005, ISBN 3-8351-0033-5 (Leitfäden der Informatik).

Wikimedia Foundation.

См. также в других словарях:

  • Reduktion — (oder als Verb: reduzieren, lateinisch reductio ‚Zurückführung‘, zu reductum Partizip II von reducere ‚reduzieren‘, ‚[auf das richtige Maß] zurückführen‘) bezeichnet: Korrektion von Messwerten die Gelände oder topografische Reduktion bei… …   Deutsch Wikipedia

  • Reduktion (Formale Sprachen) — Eine Ableitung ist in der Theoretischen Informatik eine Folge von Ableitungsschritten, die anhand einer formalen Grammatik ein Wort einer formalen Sprache erzeugt. Zur übersichtlichen Darstellung dieser Schritte verwendet man häufig Syntaxbäume.… …   Deutsch Wikipedia

  • Cook-Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Karp-Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polinomielle Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomiale Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomialzeit-Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynomielle Reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • Polynominale reduktion — Eine Polynomialzeitreduktion (auch: polynomielle Reduktion) ist eine spezielle Form der Reduktion. Zusätzlich zur Reduzierbarkeit wird hier gefordert, dass die Reduktion deterministisch in Polynomialzeit berechnet werden kann. Polynomiell… …   Deutsch Wikipedia

  • LOGSPACE-Reduktion — Eine logarithmisch platzbeschränkte Reduktion (auch als logarithmische Reduktion bezeichnet) ist eine spezielle Form der Reduktion. Neben der Forderung, dass eine Sprache L auf eine andere Sprache L mittels einer Funktion reduzierbar ist, muss… …   Deutsch Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»