Reduktion (theoretische Informatik)

Die Reduktion i​st eine Methode d​er theoretischen Informatik, b​ei der e​in Problem a​uf ein anderes zurückgeführt wird. Gibt e​s einen Algorithmus für d​as zweite Problem, s​o lässt s​ich über d​ie Reduktion a​uch das e​rste lösen. Die Reduzierbarkeit i​st daher e​ine Relation a​uf der Menge d​er Probleme, d​urch welche d​ie Berechenbarkeit o​der die Komplexität zweier Probleme zueinander i​n Bezug gesetzt werden kann.

Der Grundgedanke, Reduktionen für d​ie Untersuchung v​on Problemen z​u verwenden, g​eht auf e​inen Aufsatz d​es Mathematikers Emil Post a​us dem Jahr 1944 zurück.[1]

Es werden verschiedene Arten v​on Reduktionen unterschieden. Die häufigsten s​ind dabei d​ie One-one- o​der Many-one-Reduktion, s​owie die Truth-table- u​nd Turing-Reduktion (letztere n​ach Alan Turing benannt). Jede v​on ihnen enthält jeweils d​ie vorangegangenen a​ls Sonderfall.

Während i​n der Berechenbarkeitstheorie m​eist der Nachweis d​es Vorhandenseins e​iner bestimmten Reduktion zwischen z​wei Problemen genügt, werden i​n der Komplexitätstheorie zusätzliche Anforderungen a​n den Ressourcenverbrauch d​er Reduktion gestellt. Gewöhnliche Ressourcen s​ind hierbei Zeit o​der Speicherplatz. Dies führt a​uf die Begriffe d​er Karp- (nach Richard M. Karp) u​nd Cook-Reduktion (nach Stephen Cook).

Abgrenzungen

Konventionen

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 ${\displaystyle \chi }$ einer Teilmenge von ${\displaystyle \mathbb {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

Seien ${\displaystyle A,B\subseteq \mathbb {N} }$ Mengen natürlicher Zahlen.

• ${\displaystyle A}$ heiße many-one-reduzierbar auf ${\displaystyle B}$ – Schreibweise ${\displaystyle A\preceq _{m}B}$ – falls es eine totale (Turing-)berechenbare Funktion ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$ gibt, für die

${\displaystyle n\in A\Leftrightarrow f(n)\in B}$

gilt.

• ${\displaystyle A}$ heiße one-one-reduzierbar auf ${\displaystyle B}$ – Schreibweise ${\displaystyle A\preceq _{1}B}$ – falls ${\displaystyle f}$ dabei injektiv gewählt werden kann.

• ${\displaystyle A}$ heiße truth-table-reduzierbar auf ${\displaystyle B}$ – Schreibweise ${\displaystyle A\preceq _{tt}B}$ – falls es eine Turingmaschine gibt, die für jede natürliche Zahl ${\displaystyle n}$ eine aussagenlogische Formel ${\displaystyle \varphi (x_{1};\cdots ;x_{k})}$ (bzw. deren Gödelnummer) und natürliche Zahlen ${\displaystyle b_{1};\cdots ;b_{k}\in \mathbb {N} }$ berechnet, so dass gilt:

${\displaystyle n\in A\Leftrightarrow \varphi (\chi _{B}(b_{1});\cdots$ ;\chi _{B}(b_{k}))=1}

Dabei kann die Stelligkeit ${\displaystyle k}$ von der Eingabe ${\displaystyle n}$ abhängig sein.

• ${\displaystyle A}$ heiße Turing-reduzierbar auf ${\displaystyle B}$ – Schreibweise ${\displaystyle A\preceq _{T}B}$ – falls es eine Orakel-Turingmaschine mit Orakel für ${\displaystyle B}$ gibt, die die charakteristische Funktion ${\displaystyle \chi _{A}}$ von ${\displaystyle A}$ berechnet.

• ${\displaystyle A}$ heiße aufzählbar reduzierbar auf ${\displaystyle B}$ – Schreibweise ${\displaystyle A\preceq _{e}B}$ – falls es einen Aufzählungsoperator ${\displaystyle \Psi }$ gibt, für den ${\displaystyle \Psi (B)=A}$ gilt.

Reduktion in der Komplexitätstheorie

Prinzipiell werden i​n der Komplexitätstheorie d​ie gleichen Reduktionen w​ie in d​er Berechenbarkeitstheorie betrachtet, allerdings d​arf deren Berechnung n​un nur e​ine (in d​er Größe d​er Eingabe) beschränkte Menge Speicher o​der Rechenzeit benötigen.

Besonders häufig werden d​abei die folgenden Typen betrachtet:

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

• Die Reduktion heiße polynomiell zeitbeschränkt oder Polynomialzeitreduktion – Schreibweise ${\displaystyle \preceq ^{p}}$ –, falls es eine Konstante ${\displaystyle c\in \mathbb {N} }$ und eine (Orakel-)Turing-Maschine gibt, die ${\displaystyle \preceq }$ berechnet und dabei für jede Eingabe ${\displaystyle n}$ nur höchstens ${\displaystyle {\mathcal {O}}(l^{c}(n))}$ viele Bit-Operationen durchführt.

• Die Reduktion heiße logarithmisch platzbeschränkt – Schreibweise ${\displaystyle \preceq ^{log}}$ –, falls eine entsprechende Turingmaschine nur höchstens ${\displaystyle {\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 (${\displaystyle \preceq _{m}^{p}}$) werden auch Karp-Reduktionen genannt und die polynomiell zeitbeschränkten Turing-Reduktionen (${\displaystyle \preceq _{T}^{p}}$) heißen Cook-Reduktionen.

Beziehungen der verschiedenen Reduktionen

Für Mengen ${\displaystyle A;B\subseteq \mathbb {N} }$ natürlicher Zahlen gilt:

${\displaystyle A\preceq _{1}B\Rightarrow A\preceq _{m}B\Rightarrow A\preceq _{tt}B\Rightarrow A\preceq _{T}B}$ sowie ${\displaystyle A\preceq _{tt}B\Rightarrow A\preceq _{e}B}$

Jede dieser Implikationen ist strikt. Im Allgemeinen sind die aufzählbare Reduktion ${\displaystyle \preceq _{e}}$ und die Turing-Reduktion ${\displaystyle \preceq _{T}}$ unvergleichbar.

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

• 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 ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$, insbesondere sind sie alle transitiv.
• Die rekursiv aufzählbaren Mengen bilden genau die minimalen Elemente von ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ bzgl. der aufzählbaren Reduktion ${\displaystyle \preceq _{e}}$.
• Bei der Turing-Reduktion ${\displaystyle \preceq _{T}}$ 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:

${\displaystyle \{2n\ |\ n\in \mathbb {N} \}\equiv _{1}\{2n+1\ |\ n\in \mathbb {N} \}}$

Beide Reduktionen werden durch die Abbildung ${\displaystyle m\mapsto m+1}$ vermittelt.

• Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das Halteproblem ${\displaystyle H}$ reduzieren lässt.

• Das spezielle Halteproblem ${\displaystyle K}$, das ${\displaystyle \varepsilon }$-Halteproblem ${\displaystyle H_{0}}$ und das allgemeine Halteproblem ${\displaystyle H}$ wiederum sind untereinander one-one-äquivalent.

• Das Komplement des speziellen Halteproblems lässt sich auf dieses Turing-reduzieren ${\displaystyle {\overline {K}}\preceq _{T}K}$. Aber offenbar gibt es keine Many-one-Reduktion ${\displaystyle {\overline {K}}\npreceq _{m}K}$, denn das Komplement ist nicht aufzählbar.

• Bezeichnet ${\displaystyle (V,E)}$ einen einfachen Graphen (seine Gödelnummer), ${\displaystyle (V,{\overline {E}})}$ sein Komplement und ${\displaystyle k}$ eine natürliche Zahl, dann ist durch ${\displaystyle ((V,E),\ k)\mapsto ((V,{\overline {E}}),\ |V|-k)}$ 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 ${\displaystyle SAT}$ reduzieren. Da letzteres selbst auch in NP liegt, heißt es NP-vollständig.

Grade

Es sei ${\displaystyle \preceq }$ eine der obigen Reduktionen, wie für alle Präordnungen ist durch

${\displaystyle A\equiv B\Leftrightarrow A\preceq B\land A\succeq B}$

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 ${\displaystyle {\mathcal {P}}(\mathbb {N} )}$ und sind durch ${\displaystyle \preceq }$ partiell geordnet. Am besten bekannt ist dabei die Struktur der Turinggrade, auch einfach ${\displaystyle T}$-Grade genannt, also die Grade bezüglich der Turing-Reduktion.

Literatur

• 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, ISBN 3-8273-7020-5 (Originaltitel: 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, 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

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