www.wikidata.de-de.nina.az

Reduktion theoretische Informatik Die Reduktion ist eine Methode der theoretischen Informatik bei der ein Problem auf ei

Reduktion (theoretische Informatik)

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.

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.

gilt.
  • heiße one-one-reduzierbar auf – Schreibweise – falls dabei injektiv gewählt werden kann.
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:

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

Grade Bearbeiten

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; 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 (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, 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, Band 50 (1944), Nr. 5, S. 284–316 (online, PDF-Datei; 4,0 MB).
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Die Reduktion ist eine Methode der theoretischen Informatik bei der ein Problem auf ein anderes zuruckgefuhrt wird Gibt es einen Algorithmus fur das zweite Problem so lasst sich uber die Reduktion auch das erste losen Die Reduzierbarkeit ist daher eine Relation auf der Menge der Probleme durch welche die Berechenbarkeit oder die Komplexitat zweier Probleme zueinander in Bezug gesetzt werden kann Der Grundgedanke Reduktionen fur die Untersuchung von Problemen zu verwenden geht auf einen Aufsatz des Mathematikers Emil Post aus dem Jahr 1944 zuruck 1 Es werden verschiedene Arten von Reduktionen unterschieden Die haufigsten sind dabei die One one oder Many one Reduktion sowie die Truth table und Turing Reduktion letztere nach Alan Turing benannt Jede von ihnen enthalt jeweils die vorangegangenen als Sonderfall Wahrend in der Berechenbarkeitstheorie meist der Nachweis des Vorhandenseins einer bestimmten Reduktion zwischen zwei Problemen genugt werden in der Komplexitatstheorie zusatzliche Anforderungen an den Ressourcenverbrauch der Reduktion gestellt Gewohnliche Ressourcen sind hierbei Zeit oder Speicherplatz Dies fuhrt auf die Begriffe der Karp nach Richard M Karp und Cook Reduktion nach Stephen Cook Inhaltsverzeichnis 1 Abgrenzungen 1 1 Konventionen 1 2 Reduktionen in der Berechenbarkeitstheorie 1 3 Reduktion in der Komplexitatstheorie 2 Beziehungen der verschiedenen Reduktionen 3 Eigenschaften und Beispiele 4 Grade 5 Literatur 6 EinzelnachweiseAbgrenzungen BearbeitenKonventionen Bearbeiten Reduktionen werden ublicherweise nur fur Entscheidungsprobleme betrachtet bei denen also gefragt wird ob einem bestimmten Objekt eine besondere Eigenschaft zukommt oder nicht Genauer genugt es sogar durch eine geeignete Godelisierung ausschliesslich Entscheidungsprobleme von Mengen naturlicher Zahlen zu betrachten Das Ziel ist also stets die charakteristische Funktion x displaystyle chi nbsp einer Teilmenge von N displaystyle mathbb N nbsp zu berechnen Dieser Ansatz hat den Vorteil dass nun die Probleme mit den Teilmengen selbst identifiziert werden konnen Es ist aber sehr leicht moglich die folgenden Definitionen auch auf Optimierungs und Suchprobleme zu ubertragen Reduktionen in der Berechenbarkeitstheorie Bearbeiten Seien A B N displaystyle A B subseteq mathbb N nbsp Mengen naturlicher Zahlen A displaystyle A nbsp heisse many one reduzierbar auf B displaystyle B nbsp Schreibweise A m B displaystyle A preceq m B nbsp falls es eine totale Turing berechenbare Funktion f N N displaystyle f colon mathbb N to mathbb N nbsp gibt fur dien A f n B displaystyle n in A Leftrightarrow f n in B nbsp dd gilt A displaystyle A nbsp heisse one one reduzierbar auf B displaystyle B nbsp Schreibweise A 1 B displaystyle A preceq 1 B nbsp falls f displaystyle f nbsp dabei injektiv gewahlt werden kann A displaystyle A nbsp heisse truth table reduzierbar auf B displaystyle B nbsp Schreibweise A t t B displaystyle A preceq tt B nbsp falls es eine Turingmaschine gibt die fur jede naturliche Zahl n displaystyle n nbsp eine aussagenlogische Formel f x 1 x k displaystyle varphi x 1 cdots x k nbsp bzw deren Godelnummer und naturliche Zahlen b 1 b k N displaystyle b 1 cdots b k in mathbb N nbsp berechnet so dass gilt n A f x B b 1 x B b k 1 displaystyle n in A Leftrightarrow varphi chi B b 1 cdots chi B b k 1 nbsp dd Dabei kann die Stelligkeit k displaystyle k nbsp von der Eingabe n displaystyle n nbsp abhangig sein A displaystyle A nbsp heisse Turing reduzierbar auf B displaystyle B nbsp Schreibweise A T B displaystyle A preceq T B nbsp falls es eine Orakel Turingmaschine mit Orakel fur B displaystyle B nbsp gibt die die charakteristische Funktion x A displaystyle chi A nbsp von A displaystyle A nbsp berechnet A displaystyle A nbsp heisse aufzahlbar reduzierbar auf B displaystyle B nbsp Schreibweise A e B displaystyle A preceq e B nbsp falls es einen Aufzahlungsoperator PS displaystyle Psi nbsp gibt fur den PS B A displaystyle Psi B A nbsp gilt Reduktion in der Komplexitatstheorie Bearbeiten Prinzipiell werden in der Komplexitatstheorie die gleichen Reduktionen wie in der Berechenbarkeitstheorie betrachtet allerdings darf deren Berechnung nun nur eine in der Grosse der Eingabe beschrankte Menge Speicher oder Rechenzeit benotigen Besonders haufig werden dabei die folgenden Typen betrachtet Sei displaystyle preceq nbsp eine der obigen Reduktionen fur eine naturliche Zahl n N displaystyle n in mathbb N nbsp sei ausserdem l n log 2 n 1 displaystyle l n lfloor log 2 n rfloor 1 nbsp die Lange der Eingabe n displaystyle n nbsp in Bits Die Reduktion heisse polynomiell zeitbeschrankt oder Polynomialzeitreduktion Schreibweise p displaystyle preceq p nbsp falls es eine Konstante c N displaystyle c in mathbb N nbsp und eine Orakel Turing Maschine gibt die displaystyle preceq nbsp berechnet und dabei fur jede Eingabe n displaystyle n nbsp nur hochstens O l c n displaystyle mathcal O l c n nbsp viele Bit Operationen durchfuhrt Die Reduktion heisse logarithmisch platzbeschrankt Schreibweise l o g displaystyle preceq log nbsp falls eine entsprechende Turingmaschine nur hochstens O log l n displaystyle mathcal O log l n nbsp Speicherzellen beschreibt Diejenigen Zellen in denen die ursprungliche Eingabe steht werden dabei nicht berucksichtigt durfen aber dann auch nicht beschrieben sondern nur gelesen werden Es ist zu beachten dass eventuelle Orakel Anfragen nur einen einzelnen Rechenschritt benotigen bzw die erhaltenen Antworten nur jeweils eine einzige Speicherzelle belegen Fur die verwendete O Notation siehe auch Landau SymboleDie polynomiell zeitbeschrankten Many one Reduktionen m p displaystyle preceq m p nbsp werden auch Karp Reduktionen genannt und die polynomiell zeitbeschrankten Turing Reduktionen T p displaystyle preceq T p nbsp heissen Cook Reduktionen Beziehungen der verschiedenen Reduktionen BearbeitenFur Mengen A B N displaystyle A B subseteq mathbb N nbsp naturlicher Zahlen gilt A 1 B A m B A t t B A T B displaystyle A preceq 1 B Rightarrow A preceq m B Rightarrow A preceq tt B Rightarrow A preceq T B nbsp sowie A t t B A e B displaystyle A preceq tt B Rightarrow A preceq e B nbsp Jede dieser Implikationen ist strikt Im Allgemeinen sind die aufzahlbare Reduktion e displaystyle preceq e nbsp und die Turing Reduktion T displaystyle preceq T nbsp unvergleichbar Die einzelnen Reduktionen unterscheiden sich im Wesentlichen darin wie oft ein hypothetischer Algorithmus fur B displaystyle B nbsp benutzt werden darf um A displaystyle A nbsp zu entscheiden Bei der Many one Reduktion wird nur fur eine einzige Zahl namlich gerade f n displaystyle f n nbsp die Zugehorigkeit zu B displaystyle B nbsp gepruft das Ergebnis muss anschliessend ohne weitere Bearbeitung ausgegeben werden Truth table Reduktionen erlauben endlich viele Anfragen der b i displaystyle b i nbsp und die anschliessende Weiterverarbeitung der gewonnenen Informationen durch f displaystyle varphi nbsp Die Formel f displaystyle varphi nbsp ist dabei in der Regel als Wahrheitswerttabelle gegeben woher auch der Name der Reduktion stammt Allerdings mussen alle Anfragen x B b i displaystyle chi B b i nbsp parallel zu einem einzigen Zeitpunkt wahrend der Berechnung erfolgen Bei der Turing Reduktion schliesslich durfen beliebig viele Anfragen zu jedem Zeitpunkt der Berechnung gestellt werden ausserdem ist es moglich das weitere Vorgehen in Abhangigkeit von den erhaltenen Antworten zu verzweigen Bei der aufzahlbaren Reduktion dagegen wird uberhaupt kein Algorithmus zur Entscheidung von B displaystyle B nbsp mehr vorausgesetzt sondern lediglich eine nicht notwendig berechenbare Aufzahlung der Menge Mit zunehmender Allgemeinheit nimmt jedoch die Trennscharfe 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 Komplexitatsklasse NP bezuglich Cook Reduktion abgeschlossen ist Eigenschaften und Beispiele BearbeitenBesteht zwischen zwei Mengen eine der obigen Reduktionen die echt schwacher als die Turing Reduktion ist und ist die zweite Menge entscheidbar oder rekursiv aufzahlbar so kommt diese Eigenschaft auch automatisch der ersten Menge zu Alle Reduktionen bilden Praordnungen auf der Potenzmenge P N displaystyle mathcal P mathbb N nbsp insbesondere sind sie alle transitiv Die rekursiv aufzahlbaren Mengen bilden genau die minimalen Elemente von P N displaystyle mathcal P mathbb N nbsp bzgl der aufzahlbaren Reduktion e displaystyle preceq e nbsp Bei der Turing Reduktion T displaystyle preceq T nbsp sind das genau die entscheidbaren Mengen Die Mengen der geraden und ungeraden naturlichen Zahlen lassen sich gegenseitig aufeinander one one reduzieren sie sind one one aquivalent 2 n n N 1 2 n 1 n N displaystyle 2n n in mathbb N equiv 1 2n 1 n in mathbb N nbsp dd Beide Reduktionen werden durch die Abbildung m m 1 displaystyle m mapsto m 1 nbsp vermittelt Eine Menge ist genau dann rekursiv aufzahlbar wenn sie sich many one auf das Halteproblem H displaystyle H nbsp reduzieren lasst Das spezielle Halteproblem K displaystyle K nbsp das e displaystyle varepsilon nbsp Halteproblem H 0 displaystyle H 0 nbsp und das allgemeine Halteproblem H displaystyle H nbsp wiederum sind untereinander one one aquivalent Das Komplement des speziellen Halteproblems lasst sich auf dieses Turing reduzieren K T K displaystyle overline K preceq T K nbsp Aber offenbar gibt es keine Many one Reduktion K m K displaystyle overline K npreceq m K nbsp denn das Komplement ist nicht aufzahlbar Bezeichnet V E displaystyle V E nbsp einen einfachen Graphen seine Godelnummer V E displaystyle V overline E nbsp sein Komplement und k displaystyle k nbsp eine naturliche Zahl dann ist durch V E k V E V k displaystyle V E k mapsto V overline E V k nbsp eine polynomiell zeitbeschrankte One one Reduktion vom Knotenuberdeckungsproblem auf das Cliquenproblem erklart Jedes Problem aus NP lasst sich polynomiell zeitbeschrankt many one auf das Erfullbarkeitsproblem der Aussagenlogik S A T displaystyle SAT nbsp reduzieren Da letzteres selbst auch in NP liegt heisst es NP vollstandig Grade BearbeitenEs sei displaystyle preceq nbsp eine der obigen Reduktionen wie fur alle Praordnungen ist durch A B A B A B displaystyle A equiv B Leftrightarrow A preceq B land A succeq B nbsp eine Aquivalenzrelation erklart Die Aquivalenzklassen werden dabei Grade genannt Auf Grund der fehlenden Antisymmetrie enthalten sie meist mehr als eine Menge ublicherweise abzahlbar unendlich viele Die Grade partitionieren P N displaystyle mathcal P mathbb N nbsp und sind durch displaystyle preceq nbsp partiell geordnet Am besten bekannt ist dabei die Struktur der Turinggrade auch einfach T displaystyle T nbsp Grade genannt also die Grade bezuglich der Turing Reduktion Literatur BearbeitenKatrin Erk Lutz Priese Theoretische Informatik Eine umfassende Einfuhrung 2 erweiterte Auflage Springer Verlag Berlin u a 2002 ISBN 3 540 42624 8 Springer Lehrbuch John E Hopcroft Rajeev Motwani Jeffrey Ullman Einfuhrung in die Automatentheorie formale Sprachen und Komplexitatstheorie 2 uberarb Auflage Pearson Studium Munchen 2002 ISBN 3 8273 7020 5 englisch Introduction to automata theory languages and computation Ubersetzt 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 Einfuhrung 3 uberarbeitete Auflage Teubner Verlag Wiesbaden 2005 ISBN 3 8351 0033 5 Leitfaden der Informatik Einzelnachweise Bearbeiten 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 Abgerufen von https de wikipedia org w index php title Reduktion theoretische Informatik amp oldid 238361534 Abgrenzungen