Reduktion (Theoretische Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
QS-Informatik

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)

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 vorangegangen 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 stets also die charakteristische Funktion \chi einer Teilmenge von \N 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 A, B \subseteq \N Mengen natürlicher Zahlen.

n \in A \Leftrightarrow f(n) \in B
gilt.
  • A heiße one-one-reduzierbar auf B – Schreibweise A \preceq_1 B – falls f dabei injektiv gewählt werden kann.
n \in A \Leftrightarrow \varphi(\chi_B(b_1);\cdots; \chi_B(b_k)) = 1
Dabei kann die Stelligkeit k von der Eingabe n abhängig sein.
  • A heiße Turing-reduzierbar auf B – Schreibweise A \preceq_T B – falls es eine Orakel-Turingmaschine mit Orakel für B gibt, die die charakteristische Funktion \chi_A von A berechnet.

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ötigten.

Besonders häufig werden dabei die folgenden Typen betrachtet:

Sei \preceq eine der obigen Reduktionen, für eine natürliche Zahl n \in \N sei außerdem l(n) = \lfloor \log_2 n \rfloor + 1 die Länge der Eingabe n in Bits.

  • Die Reduktion heiße polynomiell zeitbeschränkt oder Polynomialzeitreduktion – Schreibweise \preceq^p – falls es eine Konstante c \in \N und eine (Orakel-)Turing-Maschine gibt, die \preceq berechnet und dabei für jede Eingabe n nur höchstens \mathcal{O}(l^c (n)) viele Bit-Operationen durchführt.
  • Die Reduktion heiße logarithmisch platzbeschränkt – Schreibweise \preceq^{log} – falls eine entsprechende Turingmaschine nur höchstens \mathcal{O}(\log l(n)) 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 (\preceq_m^p) werden auch Karp-Reduktionen genannt und die polynomiell zeitbeschränkten Turing-Reduktionen (\preceq_T^p) heißen Cook-Reduktionen.

Beziehungen der verschiedenen Reduktionen[Bearbeiten]

Für Mengen A;B \subseteq \N natürlicher Zahlen gilt:

A \preceq_1 B \Rightarrow A \preceq_m B \Rightarrow A \preceq_{tt} B \Rightarrow A \preceq_T B

Jede dieser Implikationen ist strikt.

Die einzelnen Reduktionen unterscheiden sich im Wesentlichen darin, wie oft ein (hypothetischer) Algorithmus für B benutzt werden darf, um A zu entscheiden. Bei der Many-one-Reduktion wird nur für eine einzige Zahl – nämlich gerade f(n) – die Zugehörigkeit zu B geprüft, das Ergebnis muss anschließend ohne weitere Bearbeitung ausgegeben werden. Truth-table-Reduktionen erlauben endlich viele Anfragen der b_i und die anschließende Weiterverarbeitung der gewonnenen Informationen durch \varphi. Die Formel \varphi ist dabei in der Regel als Wahrheitswerttabelle gegeben, woher auch der Name der Reduktion stammt. Allerdings müssen alle Anfragen \chi_B(b_i) 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.

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 Reduktion und ist die zweite entscheidbar oder rekursiv aufzählbar, so kommt diese Eigenschaft auch automatisch der ersten Menge zu.
  • Die Mengen der geraden und ungeraden natürlichen Zahlen lassen sich gegenseitig aufeinander one-one-reduzieren, sie sind one-one-äquivalent:
\{2n\ |\ n \in \N \} \equiv_1 \{ 2n+1\ |\ n \in \N \}
Beide Reduktionen werden durch die Abbildung m \mapsto m+1 vermittelt.
  • Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das Halteproblem H reduzieren lässt.
  • Das spezielle Halteproblem K, das \varepsilon-Halteproblem H_0 und das allgemeine Halteproblem H wiederum sind untereinander one-one-äquivalent.
  • Das Komplement des speziellen Halteproblem lässt sich auf dieses Turing-reduzieren \overline{K} \preceq_T K. Aber offenbar gibt es keine Many-one-Reduktion \overline{K} \npreceq_m K, denn das Komplement ist nicht aufzählbar.

Literatur[Bearbeiten]

  • Katrin Erk, Lutz Priese: Theoretische Informatik. Eine umfassende Einführung; 2. erweiterte Auflage; Springer-Verlag, 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 (Originaltitel: Introduction to automata theory, languages, and computation, übersetzt von Sigrid Richter, Ingrid Tokar), 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-Verlag, Wiesbaden 2005, ISBN 3-8351-0033-5 (Leitfäden der Informatik)

Einzelnachweise[Bearbeiten]

  1. E. Post: Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, vol. 50 (1944), no. 5, pp. 284–316 (online, PDF-Datei; 4,0 MB)