Reduktion (Komplexität) - Reduction (complexity)

Beispiel für eine Reduktion von der Booleschen Erfüllbarkeitsproblem ( A ∨ B ) ∧ (¬ A ∨ ¬ B ∨ ¬ C ) ∧ (¬ A ∨ B ∨ C ) zu einem Scheitelpunkt Abdeckung Problem . Die blauen Ecken bilden eine minimale Eckenabdeckung, und die blauen Ecken im grauen Oval entsprechen einer befriedigenden Wahrheitszuordnung für die ursprüngliche Formel.

In der Berechenbarkeitstheorie und der Computational Complexity Theory ist eine Reduktion ein Algorithmus zur Transformation eines Problems in ein anderes Problem. Eine hinreichend effiziente Reduktion von einem Problem auf ein anderes kann verwendet werden, um zu zeigen, dass das zweite Problem mindestens so schwierig ist wie das erste.

Intuitiv Problem A ist reduzierbar auf Problem B , wenn ein Algorithmus zur Lösung von Problem B effizient (wenn es existiert) auch als ein Unterprogramm verwendet werden könnten , Problem zu lösen A effizient. Wenn dies der Fall ist, die Lösung von A kann nicht härter sein als Lösung B . „Härter“ bedeutet eine höhere Schätzung der erforderlichen Rechenressourcen in einem gegebenen Kontext Atomen (zB höhere zeitliche Komplexität , höherer Speicherbedarf und teure Notwendigkeit für zusätzliche Hardware - Prozessorkerne für eine parallele Lösung im Vergleich zu einer Single-Threaded - Lösung, etc.) . Die Existenz einer Reduktion von A nach B kann in der Kurzschreibweise A ≤ m B geschrieben werden , normalerweise mit einem Index auf dem ≤, um den verwendeten Reduktionstyp anzugeben (m: Mapping-Reduktion , p: Polynomial-Reduction ).

Die mathematische Struktur, die auf einer Reihe von Problemen durch die Reduktionen eines bestimmten Typs erzeugt wird, bildet im Allgemeinen eine Vorordnung , deren Äquivalenzklassen verwendet werden können, um Unlösbarkeitsgrade und Komplexitätsklassen zu definieren .

Einführung

Es gibt zwei Hauptsituationen, in denen wir Reduzierungen verwenden müssen:

  • Erstens versuchen wir, ein Problem zu lösen, das einem Problem ähnelt, das wir bereits gelöst haben. In diesen Fällen besteht ein schneller Weg zur Lösung des neuen Problems oft darin, jede Instanz des neuen Problems in Instanzen des alten Problems umzuwandeln, diese mit unserer bestehenden Lösung zu lösen und diese dann zu verwenden, um unsere endgültige Lösung zu erhalten. Dies ist vielleicht die offensichtlichste Verwendung von Kürzungen.
  • Zweitens: Angenommen, wir haben ein Problem, von dem wir bewiesen haben, dass es schwer zu lösen ist, und wir haben ein ähnliches neues Problem. Wir könnten vermuten, dass es auch schwer zu lösen ist. Wir argumentieren durch Widerspruch: Angenommen, das neue Problem ist leicht zu lösen. Wenn wir dann zeigen können, dass jede Instanz des alten Problems leicht gelöst werden kann, indem wir sie in Instanzen des neuen Problems umwandeln und diese lösen, haben wir einen Widerspruch. Dies stellt fest, dass das neue Problem auch schwer ist.

Ein sehr einfaches Beispiel für eine Reduktion ist die Multiplikation zur Quadrierung . Angenommen, wir können nur addieren, subtrahieren, Quadrate nehmen und durch zwei dividieren. Wir können dieses Wissen verwenden, kombiniert mit der folgenden Formel, um das Produkt zweier beliebiger Zahlen zu erhalten:

Wir haben auch eine Reduzierung in die andere Richtung; Wenn wir zwei Zahlen multiplizieren können, können wir natürlich eine Zahl quadrieren. Dies scheint zu implizieren, dass diese beiden Probleme gleich schwer sind. Diese Art der Reduktion entspricht der Turing-Reduktion .

Wesentlich schwieriger wird die Reduktion jedoch, wenn wir die Einschränkung hinzufügen, dass wir die Quadrierungsfunktion nur einmal und nur am Ende verwenden können. In diesem Fall gibt es, selbst wenn wir alle grundlegenden arithmetischen Operationen einschließlich der Multiplikation verwenden dürfen, im Allgemeinen keine Reduktion, denn um das gewünschte Ergebnis als Quadrat zu erhalten, müssen wir zuerst seine Quadratwurzel berechnen, und dieses Quadrat Wurzel könnte eine seine irrationale Zahl wie das kann nicht durch arithmetische Operationen auf rationale Zahlen konstruiert werden. In die andere Richtung können wir jedoch sicherlich eine Zahl mit nur einer Multiplikation quadrieren, nur am Ende. Mit dieser eingeschränkten Form der Reduktion haben wir das nicht überraschende Ergebnis gezeigt, dass Multiplikation im Allgemeinen schwieriger ist als Quadrieren. Dies entspricht einer Viele-Eins-Reduktion .

Eigenschaften

Eine Reduktion ist eine Vorordnung , also eine reflexive und transitive Beziehung , auf P ( N )× P ( N ), wobei P ( N ) die Potenzmenge der natürlichen Zahlen ist .

Arten und Anwendungen von Ermäßigungen

Wie im obigen Beispiel beschrieben, gibt es zwei Hauptarten von Reduktionen, die bei der Rechenkomplexität verwendet werden, die Viele-Eins-Reduktion und die Turing-Reduktion . Viele-Eins-Reduktionen bilden Instanzen eines Problems auf Instanzen eines anderen ab; Turing-Reduktionen berechnen die Lösung eines Problems unter der Annahme, dass das andere Problem leicht zu lösen ist. Die Viele-Eins-Reduktion ist eine stärkere Art der Turing-Reduktion und ist effektiver bei der Aufteilung von Problemen in verschiedene Komplexitätsklassen. Allerdings erschweren die verstärkten Beschränkungen für Many-One-Reduktionen ihre Auffindbarkeit.

Ein Problem ist für eine Komplexitätsklasse vollständig, wenn jedes Problem in der Klasse auf dieses Problem reduziert wird und es auch in der Klasse selbst ist. In diesem Sinne repräsentiert das Problem die Klasse, da jede Lösung davon in Kombination mit den Reduktionen verwendet werden kann, um jedes Problem in der Klasse zu lösen.

Um jedoch nützlich zu sein, müssen Reduzierungen einfach sein . Zum Beispiel ist es durchaus möglich, ein schwer zu lösendes NP-vollständiges Problem wie das boolesche Erfüllbarkeitsproblem auf ein triviales Problem zu reduzieren, wie etwa die Bestimmung, ob eine Zahl gleich Null ist, indem die Reduktionsmaschine das Problem in exponentieller Zeit löst und Null ausgibt nur wenn es eine lösung gibt. Dies bringt jedoch nicht viel, denn obwohl wir das neue Problem lösen können, ist die Durchführung der Reduktion genauso schwierig wie das Lösen des alten Problems. Ebenso kann eine Reduktion, die eine nicht berechenbare Funktion berechnet , ein unentscheidbares Problem auf ein entscheidbares reduzieren . Wie Michael Sipser in der Einführung in die Rechentheorie betont : "Die Reduktion muss einfach sein, bezogen auf die Komplexität typischer Probleme in der Klasse [...] Wenn die Reduktion selbst schwer zu berechnen wäre, eine einfache Lösung der vollständigen Problem würde nicht unbedingt eine einfache Lösung für die Probleme ergeben, die darauf reduziert werden."

Daher hängt der geeignete Begriff der Reduktion von der untersuchten Komplexitätsklasse ab. Beim Studium der Komplexitätsklasse NP und härteren Klassen wie der polynomialen Hierarchie werden Polynomialzeitreduktionen verwendet. Beim Studieren von Klassen innerhalb von P wie NC und NL werden Log-Space-Reduktionen verwendet. Reduktionen werden auch in der Berechenbarkeitstheorie verwendet, um zu zeigen, ob Probleme durch Maschinen überhaupt lösbar sind oder nicht; in diesem Fall sind Reduktionen nur auf berechenbare Funktionen beschränkt .

Bei Optimierungsproblemen (Maximierung oder Minimierung) denken wir oft an approximationserhaltende Reduktion . Angenommen, wir haben zwei Optimierungsprobleme, so dass Instanzen eines Problems auf Instanzen des anderen abgebildet werden können, sodass nahezu optimale Lösungen für Instanzen des letzteren Problems zurücktransformiert werden können, um nahezu optimale Lösungen für das erstere zu erhalten. Auf diese Weise erhalten wir, wenn wir einen Optimierungsalgorithmus (oder Approximationsalgorithmus ) haben, der nahezu optimale (oder optimale) Lösungen für Instanzen von Problem B findet, und eine effiziente approximationserhaltende Reduktion von Problem A auf Problem B durch Komposition eine Optimierung Algorithmus, der nahezu optimale Lösungen für Instanzen von Problem A liefert. Approximationserhaltende Reduktionen werden oft verwendet, um die Härte von Approximationsergebnissen zu beweisen : wenn ein Optimierungsproblem A (unter einer gewissen Komplexitätsannahme) innerhalb eines Faktors besser als α für einige α, und es gibt eine β-Approximation-erhaltende Reduktion von Problem A auf Problem B, können wir schlussfolgern, dass Problem B innerhalb des Faktors α/β schwer zu approximieren ist.

Beispiele

Detailliertes Beispiel

Das folgende Beispiel zeigt, wie man die Reduktion des Halteproblems verwendet, um zu beweisen, dass eine Sprache unentscheidbar ist. Angenommen, H ( M , w ) ist das Problem der Bestimmung, ob eine gegebene Turingmaschine M an der Eingabezeichenfolge w anhält (durch Akzeptieren oder Zurückweisen) . Diese Sprache ist bekanntlich unentscheidbar. Angenommen, E ( M ) ist das Problem der Bestimmung, ob die Sprache, die eine gegebene Turing-Maschine M akzeptiert, leer ist (mit anderen Worten, ob M überhaupt Strings akzeptiert). Wir zeigen, dass E durch eine Reduktion von H unentscheidbar ist .

Um einen Widerspruch zu erhalten, sei R ein Entscheider für E . Wir verwenden dies, um einen Entscheider S für H zu erzeugen (von dem wir wissen, dass er nicht existiert). Gegebenen Eingangs M und w (a Turing Maschine und einige Eingabezeichenfolge), definieren , S ( M , w ) mit dem folgenden Verhalten: S schafft eine Turing Maschine N , die nur , wenn die Eingabezeichenfolge übernimmt N ist , w und M stoppt am Eingabe w , und hält sonst nicht an. Der Entscheider S kann nun R ( N ) auswerten , um zu prüfen, ob die von N akzeptierte Sprache leer ist. Wenn R N akzeptiert , dann ist die von N akzeptierte Sprache leer, so dass insbesondere M bei der Eingabe w nicht anhält , sodass S ablehnen kann. Wenn R N ablehnt , dann ist die von N akzeptierte Sprache nicht leer, also hält M bei der Eingabe w an , also kann S akzeptieren. Wenn wir also einen Entscheider R für E hätten, könnten wir einen Entscheider S für das Halteproblem H ( M , w ) für jede Maschine M und Eingabe w erzeugen . Da wir wissen, dass ein solches S nicht existieren kann, folgt, dass auch die Sprache E unentscheidbar ist.

Siehe auch

Verweise

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein, Introduction to Algorithms, MIT Press, 2001, ISBN  978-0-262-03293-3
  • Hartley Rogers, Jr.: Theorie rekursiver Funktionen und effektiver Berechenbarkeit, McGraw-Hill, 1967, ISBN  978-0-262-68052-3 .
  • Peter Bürgisser: Vollständigkeit und Reduktion in der algebraischen Komplexitätstheorie, Springer, 2000, ISBN  978-3-540-66752-0 .
  • ER Griffor: Handbook of Computability Theory, Nordholland, 1999, ISBN  978-0-444-89882-1 .