2A02:1210:7E3A:B200:D082:E64D:B90F:AD5B am 18. November 2023 um 16:49 Uhr

2023-11-18T16:49:49Z

Neue Seite

Die '''Reduktion''' ist eine Methode der [[Theoretische Informatik|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 (Mathematik)|Relation]] auf der Menge der Probleme, durch welche die [[Berechenbarkeit]] oder die [[Komplexität (Informatik)|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 Leon Post|Emil Post]] aus dem Jahr 1944 zurück.<ref>{{Literatur |Autor=Emil Post |Titel=Recursively enumerable sets of positive integers and their decision problems |Sammelwerk=[[Bulletin of the American Mathematical Society]] |Band=50 |Datum=1944 |Nummer=5 |Seiten=284–316 |Sprache=en |Online=https://www.ams.org/journals/bull/1944-50-05/S0002-9904-1944-08111-1/S0002-9904-1944-08111-1.pdf |Format=PDF |KBytes=4000}}</ref>

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 ==

=== Konventionen ===

Reduktionen werden üblicherweise nur für [[Entscheidungsproblem]]e 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 [[Menge (Mathematik)|Mengen]] [[Natürliche Zahlen|natürlicher Zahlen]] zu betrachten.
Das Ziel ist also stets, die [[Indikatorfunktion|charakteristische Funktion]] <math>\chi</math> einer [[Teilmenge]] von <math>\N</math> zu [[berechenbare Funktion|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 [[Optimierungsproblem|Optimierungs-]] und [[Suchproblem]]e zu übertragen.

=== Reduktionen in der Berechenbarkeitstheorie ===

Seien <math>A, B \subseteq \N</math> Mengen natürlicher Zahlen.

* <math>A</math> heiße ''many-one-reduzierbar'' auf <math>B</math> – Schreibweise <math>A \preceq_m B</math> – falls es eine [[Totale Funktion|totale]] [[berechenbare Funktion|(Turing-)berechenbare Funktion]] <math>f \colon \N \to \N</math> gibt, für die
*:<math>n \in A \Leftrightarrow f(n) \in B</math>
:gilt.

* <math>A</math> heiße ''one-one-reduzierbar'' auf <math>B</math> – Schreibweise <math>A \preceq_1 B</math> – falls <math>f</math> dabei [[Injektive Funktion|injektiv]] gewählt werden kann.
* <math>A</math> heiße ''truth-table-reduzierbar'' auf <math>B</math> – Schreibweise <math>A\preceq_{tt} B</math> – falls es eine [[Turingmaschine]] gibt, die für jede natürliche Zahl <math>n</math> eine [[Aussagenlogik|aussagenlogische Formel]] <math>\varphi(x_1;\cdots;x_k)</math> (bzw. deren [[Gödelnummer]]) und natürliche Zahlen <math>b_1;\cdots;b_k \in \N</math> berechnet, so dass gilt:
*:<math>n \in A \Leftrightarrow \varphi(\chi_B(b_1);\cdots; \chi_B(b_k)) = 1</math>
:Dabei kann die [[Stelligkeit]] <math>k</math> von der Eingabe <math>n</math> abhängig sein.

* <math>A</math> heiße ''Turing-reduzierbar'' auf <math>B</math> – Schreibweise <math>A \preceq_T B</math> – falls es eine [[Orakel-Turingmaschine]] mit Orakel für <math>B</math> gibt, die die charakteristische Funktion <math>\chi_A</math> von <math>A</math> berechnet.
* <math>A</math> heiße ''aufzählbar reduzierbar'' auf <math>B</math> – Schreibweise <math>A \preceq_e B</math> – falls es einen [[Aufzählungsoperator]] <math>\Psi</math> gibt, für den <math>\Psi(B) = A</math> gilt.

=== Reduktion in der Komplexitätstheorie ===

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 <math>\preceq</math> eine der obigen Reduktionen, für eine natürliche Zahl <math>n \in \N</math> sei außerdem <math>l(n) = \lfloor \log_2 n \rfloor + 1</math> die Länge der Eingabe <math>n</math> in [[Bit]]s.

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

== Beziehungen der verschiedenen Reduktionen ==

Für Mengen <math>A;B \subseteq \N</math> natürlicher Zahlen gilt:
:<math>A \preceq_1 B \Rightarrow A \preceq_m B \Rightarrow A \preceq_{tt} B \Rightarrow A \preceq_T B</math> sowie <math>A \preceq_{tt} B \Rightarrow A \preceq_e B</math>
Jede dieser Implikationen ist strikt.
Im Allgemeinen sind die aufzählbare Reduktion <math>\preceq_e</math> und die Turing-Reduktion <math>\preceq_T</math> unvergleichbar.

Die einzelnen Reduktionen unterscheiden sich im Wesentlichen darin, wie oft ein (hypothetischer) Algorithmus für <math>B</math> benutzt werden darf, um <math>A</math> zu entscheiden.
Bei der Many-one-Reduktion wird nur für eine einzige Zahl – nämlich gerade <math>f(n)</math> – die Zugehörigkeit zu <math>B</math> geprüft, das Ergebnis muss anschließend ohne weitere Bearbeitung ausgegeben werden.
Truth-table-Reduktionen erlauben endlich viele Anfragen der <math>b_i</math> und die anschließende Weiterverarbeitung der gewonnenen Informationen durch <math>\varphi</math>.
Die Formel <math>\varphi</math> ist dabei in der Regel als [[Wahrheitswerttabelle]] gegeben, woher auch der Name der Reduktion stammt.
Allerdings müssen alle Anfragen <math>\chi_B(b_i)</math> 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 <math>B</math> mehr vorausgesetzt, sondern lediglich eine (nicht notwendig berechenbare) [[Rekursiv aufzählbar|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 (Mengenlehre)|Komplement]] unterschieden werden.
Aus diesem Grund ist zum Beispiel nicht bekannt, ob die [[Komplexitätsklasse]] [[NP (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äordnung]]en auf der [[Potenzmenge]] <math>\mathcal{P}(\N)</math>, insbesondere sind sie alle [[Transitive Relation|transitiv]].
* Die [[Rekursiv aufzählbare Menge|rekursiv aufzählbaren Mengen]] bilden genau die [[Minimales Element|minimalen Elemente]] von <math>\mathcal{P}(\N)</math> bzgl. der aufzählbaren Reduktion <math>\preceq_e</math>.
* Bei der Turing-Reduktion <math>\preceq_T</math> sind das genau die [[entscheidbar]]en Mengen.
* Die Mengen der [[Parität (Mathematik)|geraden und ungeraden]] natürlichen Zahlen lassen sich gegenseitig aufeinander one-one-reduzieren, sie sind ''one-one-äquivalent'':
*:<math>\{2n\ |\ n \in \N \} \equiv_1 \{ 2n+1\ |\ n \in \N \}</math>
:Beide Reduktionen werden durch die Abbildung <math>m \mapsto m+1</math> vermittelt.

* Eine Menge ist genau dann rekursiv aufzählbar, wenn sie sich many-one auf das ''[[Halteproblem]]'' <math>H</math> reduzieren lässt.
* Das ''spezielle Halteproblem'' <math>K</math>, das <math>\varepsilon</math>''-Halteproblem'' <math>H_0</math> und das allgemeine Halteproblem <math>H</math> wiederum sind untereinander one-one-äquivalent.
* Das Komplement des speziellen Halteproblems lässt sich auf dieses Turing-reduzieren <math>\overline{K} \preceq_T K</math>. Aber offenbar gibt es keine Many-one-Reduktion <math>\overline{K} \npreceq_m K</math>, denn das Komplement ist nicht aufzählbar.
* Bezeichnet <math>(V,E)</math> einen [[Einfacher Graph|einfachen Graphen]] (seine Gödelnummer), <math>(V,\overline E)</math> sein [[Komplementgraph|Komplement]] und <math>k</math> eine natürliche Zahl, dann ist durch <math>((V,E),\ k) \mapsto ((V,\overline E),\ |V|-k )</math> 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]] <math>SAT</math> reduzieren. Da letzteres selbst auch in NP liegt, heißt es ''[[NP-vollständig]]''.

== Grade ==

Es sei <math>\preceq</math> eine der obigen Reduktionen, wie für alle Präordnungen ist durch
:<math>A \equiv B \Leftrightarrow A \preceq B \land A \succeq B</math>
eine [[Äquivalenzrelation]] erklärt.
Die [[Äquivalenzklasse]]n werden dabei ''Grade'' genannt.
Auf Grund der fehlenden [[Antisymmetrische Relation|Antisymmetrie]] enthalten sie meist mehr als eine Menge, üblicherweise [[abzählbar unendlich]] viele.
Die Grade [[Partition (Mengenlehre)|partitionieren]] <math>\mathcal{P}(\N)</math> und sind durch <math>\preceq</math> [[Halbordnung|partiell geordnet]].
Am besten bekannt ist dabei die Struktur der [[Turinggrad]]e, auch einfach <math>T</math>-Grade genannt, also die Grade bezüglich der Turing-Reduktion.

== Literatur ==

* {{Literatur |Autor=Katrin Erk, Lutz Priese |Titel=Theoretische Informatik. Eine umfassende Einführung |Auflage=2. erweiterte |Verlag=Springer |Ort=Berlin u. a. |Datum=2002 |ISBN=3-540-42624-8 |Reihe=Springer-Lehrbuch}}
* {{BibISBN|3827370205}}
* {{Literatur |Autor=Hartley Rogers, Jr. |Titel=Theory of Recursive Functions and Effective Computability |Verlag=McGraw-Hill |Ort=New York NY u. a. |Datum=1967 |Reihe=McGraw-Hill Series in Higher Mathematics |Sprache=en |Kommentar=Nachdruck: [[MIT Press]], Cambridge MA <abbr title="und andere">u. a.</abbr> 1987, ISBN 0-262-68052-1}}
* {{Literatur |Autor=[[Ingo Wegener]] |Titel=Theoretische Informatik. Eine algorithmische Einführung |Auflage=3. überarbeitete |Verlag=Teubner |Ort=Wiesbaden |Datum=2005 |ISBN=3-8351-0033-5 |Reihe=Leitfäden der Informatik}}

== Einzelnachweise ==
<references />

[[Kategorie:Berechenbarkeitstheorie]]
[[Kategorie:Komplexitätstheorie]]

Reduktion (theoretische Informatik) - Versionsgeschichte

2A02:1210:7E3A:B200:D082:E64D:B90F:AD5B am 18. November 2023 um 16:49 Uhr