Reduktion (theoretische Informatik)

Algorithmus

Die Reduktion ist eine Methode der theoretischen Informatik, bei der ein Problem auf ein anderes zurückgeführt wird. Gibt es einen Algorithmus für das zweite Problem, so lässt sich über die Reduktion auch das erste lösen. Die Reduzierbarkeit ist daher eine Relation auf der Menge der Probleme, durch welche die Berechenbarkeit oder die Komplexität zweier Probleme zueinander in Bezug gesetzt werden kann.

Der Grundgedanke, Reduktionen für die Untersuchung von Problemen zu verwenden, geht auf einen Aufsatz des Mathematikers Emil Post aus dem Jahr 1944 zurück.[1]

Es werden verschiedene Arten von Reduktionen unterschieden. Die häufigsten sind dabei die One-one- oder Many-one-Reduktion, sowie die Truth-table- und Turing-Reduktion (letztere nach Alan Turing benannt). Jede von ihnen enthält jeweils die vorangegangenen als Sonderfall.

Während in der Berechenbarkeitstheorie meist der Nachweis des Vorhandenseins einer bestimmten Reduktion zwischen zwei Problemen genügt, werden in der Komplexitätstheorie zusätzliche Anforderungen an den Ressourcenverbrauch der Reduktion gestellt. Gewöhnliche Ressourcen sind hierbei Zeit oder Speicherplatz. Dies führt auf die Begriffe der Karp- (nach Richard M. Karp) und Cook-Reduktion (nach Stephen Cook).

Abgrenzungen

Bearbeiten

Konventionen

Bearbeiten

Reduktionen werden üblicherweise nur für Entscheidungsprobleme betrachtet, bei denen also gefragt wird, ob einem bestimmten Objekt eine besondere Eigenschaft zukommt oder nicht. Genauer genügt es sogar – durch eine geeignete Gödelisierung – ausschließlich Entscheidungsprobleme von Mengen natürlicher Zahlen zu betrachten. Das Ziel ist also stets, die charakteristische Funktion   einer Teilmenge von   zu berechnen. Dieser Ansatz hat den Vorteil, dass nun die Probleme mit den Teilmengen selbst identifiziert werden können. Es ist aber sehr leicht möglich, die folgenden Definitionen auch auf Optimierungs- und Suchprobleme zu übertragen.

Reduktionen in der Berechenbarkeitstheorie

Bearbeiten

Seien   Mengen natürlicher Zahlen.

  •   heiße many-one-reduzierbar auf   – Schreibweise   – falls es eine totale (Turing-)berechenbare Funktion   gibt, für die
     
gilt.
  •   heiße one-one-reduzierbar auf   – Schreibweise   – falls   dabei injektiv gewählt werden kann.
  •   heiße truth-table-reduzierbar auf   – Schreibweise   – falls es eine Turingmaschine gibt, die für jede natürliche Zahl   eine aussagenlogische Formel   (bzw. deren Gödelnummer) und natürliche Zahlen   berechnet, so dass gilt:
     
Dabei kann die Stelligkeit   von der Eingabe   abhängig sein.
  •   heiße Turing-reduzierbar auf   – Schreibweise   – falls es eine Orakel-Turingmaschine mit Orakel für   gibt, die die charakteristische Funktion   von   berechnet.
  •   heiße aufzählbar reduzierbar auf   – Schreibweise   – falls es einen Aufzählungsoperator   gibt, für den   gilt.

Reduktion in der Komplexitätstheorie

Bearbeiten

Prinzipiell werden in der Komplexitätstheorie die gleichen Reduktionen wie in der Berechenbarkeitstheorie betrachtet, allerdings darf deren Berechnung nun nur eine (in der Größe der Eingabe) beschränkte Menge Speicher oder Rechenzeit benötigen.

Besonders häufig werden dabei die folgenden Typen betrachtet:

Sei   eine der obigen Reduktionen, für eine natürliche Zahl   sei außerdem   die Länge der Eingabe   in Bits.

  • Die Reduktion heiße polynomiell zeitbeschränkt oder Polynomialzeitreduktion – Schreibweise   –, falls es eine Konstante   und eine (Orakel-)Turing-Maschine gibt, die   berechnet und dabei für jede Eingabe   nur höchstens   viele Bit-Operationen durchführt.
  • Die Reduktion heiße logarithmisch platzbeschränkt – Schreibweise   –, falls eine entsprechende Turingmaschine nur höchstens   Speicherzellen beschreibt. Diejenigen Zellen, in denen die ursprüngliche Eingabe steht, werden dabei nicht berücksichtigt, dürfen aber dann auch nicht beschrieben, sondern nur gelesen werden.

Es ist zu beachten, dass eventuelle Orakel-Anfragen nur einen einzelnen Rechenschritt benötigen bzw. die erhaltenen Antworten nur jeweils eine einzige Speicherzelle belegen. Für die verwendete O-Notation siehe auch: Landau-Symbole

Die polynomiell zeitbeschränkten Many-one-Reduktionen ( ) werden auch Karp-Reduktionen genannt und die polynomiell zeitbeschränkten Turing-Reduktionen ( ) heißen Cook-Reduktionen.

Beziehungen der verschiedenen Reduktionen

Bearbeiten

Für Mengen   natürlicher Zahlen gilt:

  sowie  

Jede dieser Implikationen ist strikt. Im Allgemeinen sind die aufzählbare Reduktion   und die Turing-Reduktion   unvergleichbar.

Die einzelnen Reduktionen unterscheiden sich im Wesentlichen darin, wie oft ein (hypothetischer) Algorithmus für   benutzt werden darf, um   zu entscheiden. Bei der Many-one-Reduktion wird nur für eine einzige Zahl – nämlich gerade   – die Zugehörigkeit zu   geprüft, das Ergebnis muss anschließend ohne weitere Bearbeitung ausgegeben werden. Truth-table-Reduktionen erlauben endlich viele Anfragen der   und die anschließende Weiterverarbeitung der gewonnenen Informationen durch  . Die Formel   ist dabei in der Regel als Wahrheitswerttabelle gegeben, woher auch der Name der Reduktion stammt. Allerdings müssen alle Anfragen   parallel zu einem einzigen Zeitpunkt während der Berechnung erfolgen. Bei der Turing-Reduktion schließlich dürfen beliebig viele Anfragen zu jedem Zeitpunkt der Berechnung gestellt werden, außerdem ist es möglich das weitere Vorgehen in Abhängigkeit von den erhaltenen Antworten zu verzweigen. Bei der aufzählbaren Reduktion dagegen wird überhaupt kein Algorithmus zur Entscheidung von   mehr vorausgesetzt, sondern lediglich eine (nicht notwendig berechenbare) Aufzählung der Menge.

Mit zunehmender Allgemeinheit nimmt jedoch die Trennschärfe der Reduktion ab, so kann zum Beispiel unter Turing-Reduktion nicht mehr zwischen einer Menge und ihrem Komplement unterschieden werden. Aus diesem Grund ist zum Beispiel nicht bekannt, ob die Komplexitätsklasse NP bezüglich Cook-Reduktion abgeschlossen ist.

Eigenschaften und Beispiele

Bearbeiten
  • Besteht zwischen zwei Mengen eine der obigen Reduktionen, die echt schwächer als die Turing-Reduktion ist, und ist die zweite Menge entscheidbar oder rekursiv aufzählbar, so kommt diese Eigenschaft auch automatisch der ersten Menge zu.
  • Alle Reduktionen bilden Präordnungen auf der Potenzmenge  , insbesondere sind sie alle transitiv.
  • Die rekursiv aufzählbaren Mengen bilden genau die minimalen Elemente von   bzgl. der aufzählbaren Reduktion  .
  • Bei der Turing-Reduktion   sind das genau die entscheidbaren Mengen.
  • Die Mengen der geraden und ungeraden natürlichen Zahlen lassen sich gegenseitig aufeinander one-one-reduzieren, sie sind one-one-äquivalent:
     
Beide Reduktionen werden durch die Abbildung   vermittelt.
  • Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das Halteproblem   reduzieren lässt.
  • Das spezielle Halteproblem  , das  -Halteproblem   und das allgemeine Halteproblem   wiederum sind untereinander one-one-äquivalent.
  • Das Komplement des speziellen Halteproblems lässt sich auf dieses Turing-reduzieren  . Aber offenbar gibt es keine Many-one-Reduktion  , denn das Komplement ist nicht aufzählbar.
  • Bezeichnet   einen einfachen Graphen (seine Gödelnummer),   sein Komplement und   eine natürliche Zahl, dann ist durch   eine polynomiell zeitbeschränkte One-one-Reduktion vom Knotenüberdeckungsproblem auf das Cliquenproblem erklärt.
  • Jedes Problem aus NP lässt sich polynomiell zeitbeschränkt many-one auf das Erfüllbarkeitsproblem der Aussagenlogik   reduzieren. Da letzteres selbst auch in NP liegt, heißt es NP-vollständig.

Es sei   eine der obigen Reduktionen, wie für alle Präordnungen ist durch

 

eine Äquivalenzrelation erklärt. Die Äquivalenzklassen werden dabei Grade genannt. Auf Grund der fehlenden Antisymmetrie enthalten sie meist mehr als eine Menge, üblicherweise abzählbar unendlich viele. Die Grade partitionieren   und sind durch   partiell geordnet. Am besten bekannt ist dabei die Struktur der Turinggrade, auch einfach  -Grade genannt, also die Grade bezüglich der Turing-Reduktion.

Literatur

Bearbeiten
  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung (= Springer-Lehrbuch). 2. erweiterte Auflage. Springer, Berlin u. a. 2002, ISBN 3-540-42624-8.
  • 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 (englisch: Introduction to automata theory, languages, and computation. Übersetzt von Sigrid Richter, Ingrid Tokar).
  • Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability (= McGraw-Hill Series in Higher Mathematics). McGraw-Hill, New York NY u. a. 1967 (englisch, Nachdruck: MIT Press, Cambridge MA u. a. 1987, ISBN 0-262-68052-1).
  • Ingo Wegener: Theoretische Informatik. Eine algorithmische Einführung (= Leitfäden der Informatik). 3. überarbeitete Auflage. Teubner, Wiesbaden 2005, ISBN 3-8351-0033-5.

Einzelnachweise

Bearbeiten
  1. Emil Post: Recursively enumerable sets of positive integers and their decision problems. In: Bulletin of the American Mathematical Society. Band 50, Nr. 5, 1944, S. 284–316 (englisch, ams.org [PDF; 4,0 MB]).