Reduktion Theoretische Informatik Beispiel Essay

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 | Quelltext bearbeiten]

Konventionen[Bearbeiten | Quelltext 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 Mengennatü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 | Quelltext bearbeiten]

Seien Mengen natürlicher Zahlen.

gilt.
Dabei kann die Stelligkeit von der Eingabe abhängig sein.

Reduktion in der Komplexitätstheorie[Bearbeiten | Quelltext 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 eine der obigen Reduktionen, für eine natürliche Zahl sei außerdem die Länge der Eingabe in Bits.

  • 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 | Quelltext 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ätsklasseNP bezüglich Cook-Reduktion abgeschlossen ist.

Eigenschaften und Beispiele[Bearbeiten | Quelltext 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 Komplement des speziellen Halteproblem lässt sich auf dieses Turing-reduzieren . Aber offenbar gibt es keine Many-one-Reduktion , denn das Komplement ist nicht aufzählbar.
  • Bezeiche 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.

Grade[Bearbeiten | Quelltext 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 | Quelltext 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 (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 MAu. 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 | Quelltext 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).

Definition:  Ein Ent­scheidungsproblem ist ein Problem, das nur zwei mögliche Lösungen hat: entweder "ja" oder "nein".

Beispiel:  Das Primzahl­problem ist ein Ent­scheidungsproblem. Das Primzahl­problem besteht darin, für eine beliebige natürliche Zahl die Frage zu beantworten: "Ist eine Primzahl?"

Wir verwenden hier den Begriff "Problem" eigentlich für eine ganze Klasse gleich­artiger Einzel­probleme. Das Primzahl­problem etwa enthält als Einzel­probleme: "Ist 1 eine Primzahl?", "Ist 2 eine Primzahl?", "Ist 3 eine Primzahl?" usw. Ein solches Einzel­problem nennen wir einen Fall (engl.: instance) des Problems. "Ist 38 eine Primzahl?" ist also ein Fall des Primzahl­problems.

Ein sehr universelles Ent­scheidungsproblem ist das Wortproblem.

Definition:  Sei ein Alphabet und * die Menge aller Wörter über . Sei ferner   * eine Sprache über . Das Wortproblem besteht darin, für ein beliebiges Wort  * folgende Frage zu beantworten: "Ist   ?"

Sei das Alphabet vorgegeben. Dann ist das Wortproblem also charakterisiert durch die ent­sprechende Sprache , und ein Fall des Wortproblems ist charakterisiert durch ein Paar (, ).

Durch eine geeignete Codierung lässt sich ein Ent­scheidungsproblem in ein Wortproblem umwandeln. Beispiels­weise kann man die natürlichen Zahlen als Wörter über  = {0, ..., 9} codieren (was man gemeinhin auch tut, indem man sie in Dezimal­darstellung schreibt). Die Primzahlen, ebenfalls in Dezimal­darstellung codiert, bilden dann eine Teilmenge der Menge aller Wörter über , nämlich die Sprache PRIMES  *. Die Frage "Ist die Zahl 789 eine Primzahl?" lässt sich nun umformulieren in "Ist das Wort 789 ein Element der Sprache PRIMES?"

Ent­scheidungsprobleme lassen sich also zurückführen auf Wortprobleme, und Wortprobleme entsprechen Sprachen. Wir können daher die Begriffe "Ent­scheidungsproblem" und "Sprache" miteinander identifizieren, wenn wir uns das Ent­scheidungsproblem als Wortproblem codiert vorstellen. Die Problemgröße eines bestimmten Falles des Wortproblems entspricht dann der Länge des Wortes.

Im Folgenden geht es darum, Ent­scheidungsprobleme durch Trans­formation ineinander umzuformen.

Definition:  Gegeben seien zwei Sprachen und über einem gemeinsamen Alphabet . Die Sprache lässt sich in die Sprache trans­formieren, wenn es eine berechenbare Abbildung : *  * gibt, derart dass für alle   * gilt

      ()  .

Diese Abbildung wird dann als Trans­formation von nach bezeichnet.

Wichtig ist, dass die Abbildung berechenbar ist und dass sie auf ganz *, also auf der Menge aller Wörter über dem Alphabet , definiert ist und nicht nur auf .

Beispiel:  Sei  = {0, ..., 9} und sei diejenige Sprache, die aus den Dezimal­darstellungen aller durch 5 teilbaren nicht­negativen ganzen Zahlen besteht, wobei führende Nullen zugelassen sind, d.h.

  =  0*{0, 5, 10, 15, 20, 25, ... }

Die Abbildung sei wie folgt definiert. Für alle Wörter   * mit  = 0 ... -1 sei

()  =  -1

d.h. wir betrachten nur die letzte Ziffer von .

Die Sprache sei nun

  =  {0, 5}.

Tatsächlich ist eine Trans­formation von nach , denn es gilt für alle Wörter   *

      ()  ,

denn eine beliebige nicht­negative ganze Zahl ist genau dann durch 5 teilbar, wenn ihre letzte Ziffer gleich 0 oder 5 ist.

Ist eine Trans­formation einer Sprache nach einer Sprache gegeben, so lässt sich das Wortproblem (, ) lösen, indem  = () berechnet wird und dann das Wortproblem (, ) gelöst wird. Man sagt dann, dass sich das Problem auf das Problem reduzieren lässt.

Indem also das Problem gelöst wird, ist damit auch gelöst. Haben wir also ein Problem­lösungs­verfahren für , haben wir damit auch eines für , indem wir die Trans­formation und das Problem­lösungs­verfahren für hinter­einander ausführen. Die Prüfung der Teilbarkeit durch 5 ist ein Beispiel hierfür.

Im täglichen Leben versuchen wir meist, schwierige Probleme, die wir nicht lösen können, auf leichtere Probleme, die wir lösen können, zu reduzieren. In Wirklichkeit aber ist es nicht möglich, ein schweres Problem auf ein leichtes Problem zu reduzieren, es sei denn, die Schwierig­keit steckt in der Trans­formation. Denn das Problem ist ja tatsächlich nicht schwierig, wenn man es leicht in ein leichtes Problem trans­formieren und dieses dann lösen kann.

Umgekehrt ist es dagegen möglich, ein leichtes Problem in ein schweres Problem zu trans­formieren, nach dem Motto: "Warum einfach, wenn's auch kompliziert geht?" Wir kleiden gewisser­maßen das leichte Problem so ein, dass es zu einem schwierigen Problem wird. Wenn wir das schwierige Problem dann lösen, fällt die Lösung des leichten Problems dabei ab.

So können wir z.B. feststellen, ob eine Zahl durch 5 teilbar ist (leichtes Problem), indem wir die Zahl in ihre Primfaktoren zerlegen (schweres Problem) und prüfen, ob die 5 unter den Primfaktoren auftritt.

Die Frage ist nun: Wenn es unmöglich ist, schwere auf leichte Probleme zu reduzieren und wenn es unsinnig ist, leichte auf schwere Probleme zu reduzieren, wozu werden dann Reduktionen überhaupt gebraucht? Die Antwort ist: Um zu zeigen, dass ein Problem mindestens so schwer ist wie ein anderes, oder dass es höchstens so schwer ist, oder dass die beiden Probleme im wesentlichen gleich schwer sind.

Aufgabe 1:  Formulieren Sie die Regel für die Teilbarkeit durch 3 als Trans­formation von einer Sprache in eine Sprache . Geben Sie , und an.

 

 

0 comments

Leave a Reply

Your email address will not be published. Required fields are marked *