NP-vollständige Probleme

Reduktion von Problemen

 aufwärts

Entscheidungsprobleme

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 m die Frage zu beantworten: "Ist m 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 A ein Alphabet und A* die Menge aller Wörter über A. Sei ferner L enthalten in A* eine Sprache über A. Das Wortproblem besteht darin, für ein beliebiges Wort w Element A* folgende Frage zu beantworten: "Ist w Element L?"

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

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 A = {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 A, nämlich die Sprache PRIMES enthalten in A*. 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.

Transformation und Reduktion

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

w Element R  genau dann wenn  f(wElement S.

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

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

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

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

Die Abbildung f sei wie folgt definiert. Für alle Wörter w Element A* mit w = w0 ... wn-1 sei

f(w)  =  wn-1

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

Die Sprache S sei nun

S  =  {0, 5}.

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

w Element R  genau dann wenn  f(wElement S,

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 f einer Sprache R nach einer Sprache S gegeben, so lässt sich das Wortproblem (w, R) lösen, indem w' = f(w) berechnet wird und dann das Wortproblem (w', S) gelöst wird. Man sagt dann, dass sich das Problem R auf das Problem S reduzieren lässt.

Indem also das Problem w' gelöst wird, ist damit auch w gelöst. Haben wir also ein Problem­lösungs­verfahren für S, haben wir damit auch eines für R, indem wir die Trans­formation f und das Problem­lösungs­verfahren für S 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 R auf ein leichtes Problem S zu reduzieren, es sei denn, die Schwierig­keit steckt in der Trans­formation. Denn das Problem R ist ja tatsächlich nicht schwierig, wenn man es leicht in ein leichtes Problem S 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.

Aufgaben

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

 

Weiter mit:   [Die Mengen P und NP]   oder   up

 

homeH.W. Lang   Hochschule Flensburg   lang@hs-flensburg.de   Impressum   ©   Created: 25.06.2002   Updated: 21.05.2016
Valid HTML 4.01 Transitional


Campus Flensburg

Informatik in Flensburg studieren...

 

Neu gestaltetes Studienangebot:

Bachelor-Studiengang
Angewandte Informatik

mit Schwerpunkten auf den Themen Software, Web, Mobile, Security und Usability.

Ihr Abschluss
nach 7 Semestern:
Bachelor of Science

 

Ebenfalls ganz neu:

Master-Studiengang
Angewandte Informatik

Ein projektorientiertes Studium auf höchstem Niveau mit den Schwerpunkten Internet-Sicherheit, Mobile Computing und Human-Computer Interaction.

Ihr Abschluss
nach 3 Semestern:
Master of Science

 

Weitere Informatik-Studienangebote an der Hochschule Flensburg:

Medieninformatik

Wirtschaftsinformatik