Schönen guten Tag zusammen.
Ich begrüße Sie zur Vorlesung Theoretische Informatik.
Wo waren wir letztes Mal stehen geblieben?
Ja, wir sind mitten im Kapitel Komplexitätsklassen.
Und wir haben das letzte Mal für mehrere Probleme gezeigt, dass sie
entweder vollständig sind.
Und heute geht es so weiter, dass wir für weitere Probleme zeigen,
dass sie entweder vollständig sind, aber mit den NP
-Vollständigkeitsbeweisen, das hat dann heute so langsam ein Ende.
Wir werden dann danach in dem Kapitel noch zwei Richtungen
weiterverfolgen.
Die eine ist die Frage, gibt es neben den Klassen P und NP, denn
weitere Komplexitätsklassen in diesem Umfeld P, NP, vor allem wenn P
ungleich NP ist, wie liegt dann, wie sieht dann die Welt innerhalb von
NP aus?
Sind da nur die NP-Vollständigen Probleme und die Probleme aus P oder
gibt es da möglicherweise noch andere Probleme?
Dreckstrich, Sprachen.
Das ist sozusagen so diese eine Richtung.
Das beinhaltet auch so ein bisschen nochmal die Frage, wie handhaben
wir denn Probleme, die nicht als Entscheidungsprobleme formuliert
sind?
Wie passen die sich ein?
Wie nennen wir ein Problem, das kein Entscheidungsproblem ist, aber
mindestens so schwer ist wie alle NP-Vollständigen
Entscheidungsprobleme?
Wie bringen wir das sozusagen in Relation zu diesen
Entscheidungsproblemen?
Und die andere Richtung ist die, mal ausgehend davon, dass P ungleich
NP ist, was macht man denn nun mit den NP-Vollständigen Problemen, die
man ja auch irgendwie mit effizienten Algorithmen, was auch immer
jetzt effizient in dem Zusammenhang heißt, lösen will.
Wir werden einen kleinen Exkurs machen in Richtung polynomiale
Algorithmen für NP-Vollständige Probleme oder allgemeine Probleme, die
mindestens so schwer sind wie NP-Vollständige Probleme.
Polynomiale Algorithmen, die vielleicht nicht genau eine optimale
Lösung für so ein Problem liefern, aber Lösungen liefern, die
beweisbar gut sind.
Das ist sozusagen die Richtung approximierender Algorithmen.
Das ist sozusagen der erste Schritt, den man in den 60er, 70er Jahren
gemacht hat, nachdem eben diese Theorie der NP-Vollständigkeit
sozusagen da stand, Satz von Kuck bewiesen war und so weiter, war dann
sozusagen der erste Ansatz.
Und was machen wir denn jetzt mit NP-Vollständigen Problemen, dass man
solche approximierenden Algorithmen entworfen hat beziehungsweise auch
negativ Resultate bezüglich polynomieller Approximierbarkeit bewiesen
hat.
Und damit werden wir dann nächste Woche das Kapitel abschließen, das
Kapitel Komplexitätsklassen und dann aber vor Weihnachten noch mit dem
nächsten Kapitel anfangen.
Das ist ein bisschen unglücklich, weil es wäre eigentlich ein guter
Schnitt, sozusagen dann im nächsten Jahr mit dem nächsten Kapitel
anzufangen.
So war das auch in den vergangenen Jahren, wenn ich die Vorlesung
gehalten habe.
Aber dieses Jahr ist irgendwie das Vorlesungsende so früh, dass ich
mir das nicht erlauben kann, dann bis nächstes Jahr zu warten mit dem
Kapitel.
So sieht es jetzt aus bis Weihnachten und insbesondere für heute.
Also weitere NP-Vollständigkeitsbeweise und dann die Frage, wie sieht
denn die Welt um P und NP aus?
Weitere NP-Vollständigkeitsbeweise.
Sie erinnern sich, das letzte Mal habe ich diesen Chart angemalt.
Also wir haben als allererstes mit dem Satz von Cook den Beweis, dass
Sat NP-Vollständig ist und dann haben wir eben eine polynomiale
Transformation von Sat auf 3Sat gemacht, von 3Sat auf Klick, von 3Sat
auf 3 Färbbarkeit von Graphen, von 3 Färbbarkeit von Graphen auf Exact
Cover und auf die Art sind wir schon in verschiedene Problembereiche
vorgestoßen, nämlich von Erfüllbarkeitsproblemen wie Sat und 3Sat, zu
Graphenproblemen wie Klick und 3 Färben von Graphen, zu
Mengenproblemen wie Exact Cover und heute geht es dann weiter zu
weiteren Problemen.
Wir werden dann weiter beweisen, dass ein Problem Subset Sam
NP -Vollständig ist und von da aus ein Problem namens Partition.
Und von da aus ein Problem namens Knapsack.
Rucksack Problem.
Diese polynomialen Transformationen führen wir durch, die sind nicht
so technisch, nicht so schwierig wie die letzte, die wir letztes Mal
hatten.
Und bei Subset Sam, Partition und Knapsack sind wir nochmal bei einer
anderen Art von Problemen.
Problemen auf Mengen, wo man Mengen geeignet aufteilen muss oder aus
einer Menge eine geeignete Teilmenge finden muss.
Also so sieht das aus.
Und danach werden wir, wie gesagt, ein bisschen thematisieren, wie die
Welt um P&NP noch aussieht.
Gleich auch schon eins vorneweg.
Knapsack ist insofern interessant, als dass das unter den NP
-Vollständigen Problemen irgendwie leichter erscheint als andere.
Und was das heißt, das werden wir auch nochmal genauer in der nächsten
Woche betrachten.
Also zu heute.
Also allererstes das Problem Subset Sam und der Beweis, dass Subset
Sam NP-Vollständig ist.
Subset Sam ist folgendermaßen definiert.
Wir haben eine endliche Grundmenge gegeben und auf dieser Grundmenge
eine Gewichtsfunktion, die jedem Element der Grundmenge ein Gewicht
zuordnet.
Und die Gewichte sind natürliche Zahlen.
Und außerdem haben wir einen Parameter K.
Das ist auch eine natürliche Zahl.
Und die Frage ist jetzt, gibt es eine Teilmenge in unserer Grundmenge,
sodass die Gewichte der Elemente dieser Teilmenge aufsummiert genau K
ergibt.
Also können wir hier Elemente aus M rausnehmen, sodass die Gewichte
dieser Elemente aufsummiert genau diesen Parameter K trifft.
Diese Elemente würden wir dann eben in diese Teilmenge M' stecken.
Dieses Problem ist NP-Vollständig.
Das sieht eigentlich ziemlich harmlos aus, würde ich sagen.
Ist NP-Vollständig.
Ein kleines Beispiel.
Aber erst mal übliche Übungen.
Als erstes zu zeigen, mein Problem ist in NP.
Das kennen Sie mittlerweile in- und auswendig, was dafür zu tun ist.
Dafür ist einfach zu tun, dass zu überprüfen, dass wenn Sie sozusagen
so ein Zertifikat dafür haben, dass eine vorgegebene Instanz des
Problems, eine Ja-Instanz ist, also eine Instanz, wo die richtige
Antwort ist.
Ja, in dem Fall, ja, es gibt eine Menge M', sodass die Gewichte der
Elemente aus M' aufsummiert K ergibt, dass Sie dies mit polynomialem,
nur polynomialem Aufwand verifizieren können.
Und was wäre hier ein Zertifikat?
Das wäre tatsächlich die Vorgegabe so einer Menge M'.
Also ich gebe Ihnen einfach so eine Menge M', Teilmenge M' vor.
Ich habe es jetzt sammelt.
NP heißt, wir können für diese Menge M' mit polynomiellem Aufwand
überprüfen, dass die Elemente, die Gewichte der Elemente, der Menge
aufsummiert gerade K ergibt.
Das ist klar.
Dafür müssen Sie einfach diese Gewichte aufsummieren und nachgucken,
ob das K ist.
Das ist natürlich polynomial in der Größe des ganzen Problems.
Gut, das ist immer, also das ist meistens, bisher war es immer so bei
allen Beispielen, die wir hatten, von Problemen aus NP, leicht zu
beweisen.
Und jetzt eben der zweite Schritt, dass wir eine polynomiale
Transformation von einem NP-vollständigen Problem auf Subset Sum
angeben können.
Und wir nehmen Exact Cover und geben eine polynomiale Transformation
von Exact Cover zu Subset Sum an.
Dafür müssen wir einfach eine Instanz von Exact Cover hernehmen und
die mit polynomialem Aufwand überführen in eine Instanz von Subset
Sum, sodass die Ja-Instanzen von Exact Cover genau auf die Ja
-Instanzen von Subset Sum abgebildet werden.
Also wir nehmen so eine Instanz von Exact Cover, die sieht so aus, sie
besteht aus einer Grundmenge X.
Der Einfachheit halber werden einfach die Elemente dieser Grundmenge
durchnummeriert von 0 bis M-1 und eine Menge S, die besteht aus
Teilmengen von X.
Die Frage ist ja, gibt es jetzt so eine Teilmenge von S, S', sodass in
den Mengen in S', jedes Element aus X genau einmal enthalten ist.
Sodass also ganz X abgedeckt wird durch die Mengen aus S', heißt jedes
Element aus X kommt in mindestens einer Menge aus S' vor.
Und das ist Cover.
Und das Cover soll exakt sein, das heißt, jedes Element aus X kommt
auch nur in höchstens einer Menge aus S'.
Also so eine Instanz nehmen wir her und daraus konstruieren wir jetzt
also eine Subset Sum-Instanz.
Eine Subset Sum-Instanz besteht aus einer Grundmenge, einer
Gewichtspunktion W auf der Grundmenge und einem Parameter K.
Und als Grundmenge nehmen wir dieses S, also das M ist eine Menge von
Mengen, die Grundmenge ist S.
Wir definieren so eine Anzahl X für jedes X, das in irgendeinem Y aus
S vorkommt.
Und Anzahl X soll einfach heißen, in wie vielen Mengen aus S kommt
denn das Element X aus X vor.
Und wir nennen P, definieren P als diese maximale Anzahl plus 1.
Maximale Anzahl der Mengen, in der irgend so ein X aus X vorkommt,
plus 1.
Und jetzt definieren wir auf der Basis die Gewichtspunktion für unser
Subset Sum-Problem.
Und zwar folgendermaßen, also es muss jedem Element aus M ein Gewicht
zugeordnet werden.
Element aus M, das ist so eine Menge aus S, also Teilmenge von X.
Und das Gewicht, das von so einer Menge Y zuordnen soll sein, Summe
über die Elemente X aus Y, P, diese Zahl hoch X.
Also ein Polynom.
Und das K, dieser Parameter hier, das soll einfach die Summe über alle
Elemente aus der Grundmenge von Exact Cover, also alle Elemente aus X,
also X gleich 0 bis M minus 1, P, dieses P hoch X sein.
Das sieht jetzt erstmal so ein bisschen gefährlich aus, was wir hier
machen, weil wir hier so Potenzen bilden, wo diese X als Exponent
vorkommen.
Ich sage gleich eins vorneweg, wir werden nicht mit diesen Werten
rechnen.
Das heißt, die Polynomialität, wenn man das einfach erstmal so
hinschreibt, von dieser Konstruktion, die ist klar.
Solange wir hier nicht mit rechnen, es gibt da keine Gefahr, dass wir
sozusagen exponentiell im Aufwand würden, exponentiell in der Größe
dieser Instanz.
So, jetzt müssen wir erstmal interpretieren, was diese
Gewichtsfunktionen dieses K eigentlich...
Das interpretieren wir folgendermaßen.
Wir wollen sozusagen Mengenzugehörigkeit von solchen kleinen X
darstellen.
Ob so ein kleines X in der Menge Y ist.
Und das stellen wir dar durch so ein Polynom, was man interpretieren
kann als eine Zahl zur Basis P. Im Prinzip die Exponenten hier, sagt
mir einfach, ob P hoch X für ein X vorkommt.
Also für irgendein X aus X, P hoch X in dem W von Y vorkommt.
Sagt mir einfach, ob das entsprechende X in dem Y ist.
Das heißt also, Mengenzugehörigkeit stellen wir da als Zahlen zur
Basis P und das kann man folgendermaßen einfach ganz einfach machen.
Nehmen wir dieses W von Y für so eine Menge Y aus S, einfach als einen
String von Nullen bis Einsen, der Länge M hinschreibt.
M ist Kardinalität unserer Menge X, Groß X, wo diese kleinen X
herkommen.
Und da steht eben an der i-ten Stelle einfach nur eine 0 oder eine 1.
Da steht eine 0, wenn das P hoch X für das konkrete X, das zu der
Stelle gehört, hier in dem Polynom zu W von Y nicht vorkommt und da
steht eine 1, wenn das P von X hier in dieser Summe vorkommt.
Also andererseits, wir kodieren das W von Y einfach als so ein Vektor,
der Länge M und an der i-ten Stelle steht genau dann Vektor, nochmal
ein Vektor der Länge M, in dem nur Nullen oder Einsen stehen und an
der i-ten Stelle steht genau dann eine 1, wenn das Element I aus X,
aus 0 bis M minus 1, in Y vorkommt.
So, und das K, das entspricht dann also einfach nur so einem Vektor
der Länge M, wo an jeder Stelle 1 steht.
Also für jedes X aus Groß X, also für X gleich 0 bis M minus 1, kommt
ja P hoch X in dieser Summe zu K vor.
Das heißt also, für jedes P von X hat man ein Koeffizient 1, oder das
heißt also, K entspricht so einem String der Länge M, wo überall
Einsen stehen.
So, jetzt könnte man einfach mal rechnen mit den Gewichten, sich
überlegen, was würde das denn heißen?
Wie kann man das darstellen bei dieser String-Schreibweise?
Ja, wenn man solche Gewichte W von Y und I und W von Y und J addieren
würde, dann bekäme man einfach an den entsprechenden Stellen in dem
String der Länge M eine Zahl, je nachdem, ob das entsprechende Element
in keiner der beiden vorkommt, dann steht da eine 0, oder in genau
einer der beiden vorkommt, dann steht da eine 1, oder in beiden
vorkommt, dann steht da eine 2.
Das heißt also, wenn wir für solche N, Y und I die W von Y und I
aufsummieren würden, dann würde eben in dem entsprechenden String an
einer bestimmten Stelle stehen, wie oft das entsprechende X insgesamt
vorkommt in den Mengen.
In wie vielen Mengen das vorkommt.
So könnte man das interpretieren.
Und wenn gerade K rauskommt, hier diese Summe, dann heißt das, in den
entsprechenden Mengen kommt jedes der Elemente aus der Grundmenge X
genau einmal, insgesamt in den Mengen kommt jedes Element genau einmal
vor.
Das heißt also, hier mit so einer Summe K zu treffen, heißt ich habe
Mengen Y aus S Strich, die genau X überdecken.
So können Sie das interpretieren.
Schauen wir uns das hier mal am Beispiel an.
Unsere Grundmenge wären 0 bis 6.
Unsere Menge S, wir sind also jetzt bei einer Instanz von ExactCover,
unsere Menge S besteht ja aus Teilmengen von X.
Teilmenge Y1 wäre 0, 1, 2, 3.
Y2 wäre 2, 5.
Y3 wäre 3, 4, 5.
Und Y4 wäre 4, 5, 6.
Bei ExactCover würden wir jetzt also eine Teilmenge von S suchen, so
dass über die Mengen in der Teilmenge X exakt überdeckt wird.
So und jetzt haben wir hier das Anzahl X für X aus X definiert, als
die Anzahl der Mengen aus S, in denen das entsprechende X vorkommt.
Also Anzahl 0 ist die Anzahl der Mengen aus S, in denen 0 vorkommt.
0 kommt nur in der ersten vor, also Anzahl 0 ist 1.
Anzahl 1, Anzahl der Mengen hier, in denen 1 vorkommt.
1 kommt nur in Y1 vor, also Anzahl 1 ist 1.
2, Anzahl der Mengen in S, in denen 2 vorkommt.
2 kommt in Y1 und Y2 vor, in den anderen beiden nicht.
Also Anzahl 2 ist 2, Anzahl 3 ist 2, weil 3 kommt hier und hier vor.
Anzahl 4 ist 2, weil 4 kommt hier und hier vor.
Anzahl 5 ist 3, denn 5 kommt in der Menge Y2, Y3 und Y4 vor.
Anzahl 6 ist 1.
Das heißt also P, was das Maximum dieser Anzahl X plus 1 ist, ist 4.
Weil maximales Vorkommen eines Elementes in Mengen vor aus S ist 3,
wie 5, das heißt also P wird als 4 definiert.
So und jetzt eben die Gewichte von Y1, Y2, Y3, Y4, gleich in der
Interpretation, was die Gewichte ausdrücken.
Also die Gewichte entsprechen einfach so einem Vektor der Länge M,
also hier der Länge 7.
Und an der i-ten Stelle steht, ob das Element I aus X in der
entsprechenden Teilmenge YJ vorkommt.
Also W1 entspricht dieser Menge und das machen wir von hinten nach
vorne.
Denn das kommt ja von diesem Polynom und ich habe gesagt, was hier ja
eigentlich steht an der entsprechenden Stelle, ist der Koeffizient,
das P von X.
6 kommt nicht vor, 5 kommt nicht vor, 4 kommt nicht vor, 3 kommt vor,
2 kommt vor, 1 kommt vor, 0 kommt vor in Y1.
Deshalb ist W von Y1 entspricht diesem String hier 0, 0, 0, 1, 1, 1,
1.
Wir haben einmal P hoch 0 und einmal P hoch 1 und einmal P hoch 2 und
einmal P hoch 3 und 0 mal P hoch 4 und 0 mal P hoch 5 und 0 mal P hoch
6.
So können Sie das hier interpretieren.
Die 4 steht hier unten für, das ist die Basis unseres Polynoms.
Bei Y2 haben wir wieder von hinten nach vorne, 0 kommt nicht vor, also
hier eine 0, 1 kommt nicht vor, also hier eine 0, 2 kommt vor, also
hier steht eine 1, 3 kommt nicht vor, also steht hier eine 0, 4 kommt
nicht vor, also steht hier eine 0, 5 kommt vor, also steht hier eine 1
und vorne steht wieder eine 0.
Also das sind sozusagen die 0, 1 Vektoren, die Sie haben, für die
Mengen Y, J aus S, die einem einfach sagen, kommt das entsprechende
Element aus X in der Menge vor oder nicht.
Und für K hätten wir einfach hier diesen Vektor, wo an jeder Stelle
eine 1 steht.
So, und jetzt unser Beweis, dass eine Ja-Instanz von XSectCover auf
eine Ja-Instanz von ZZSAM abgebildet wird und umgekehrt.
Also steht hier so, also Ja-Instanz von XSectCover, also unser XS ist
lösbar.
Ja, es gibt eine exakte Überdeckung.
Zu zeigen, daraus folgt, die Instanz von ZZSAM MWK ist lösbar.
Es gibt so eine Teilmenge von M, deren Gewicht gerade genau K ist.
Sei also S' eine Lösung von XSectCover, also eine exakte Überdeckung
von X, S.
Was gilt dann?
Ja, dann gilt, dass die Y aus S' aufsummiert über die Y aus S', diese
W von Y, das ist ja nichts anderes als Summe über Y aus S', Summe X
aus Y, P von P hoch X, genau X gleich 0 bis M minus 1, P von X ist.
Jedes X kommt hier genau einmal vor in der Summe.
Das ist genau diese Summe.
Das ist genau das K, wie wir das K definiert haben.
Also von da nach da ist offensichtlich, da jedes X genau einmal
überdeckt wird, kommt hier also genau in der Summe K raus.
Also S' ist auch gleichzeitig eine Lösung für unsere Instanz, die wir
gebaut haben von XSectCover und umgekehrt genauso.
Jetzt hätten wir also eine Menge S' aus M, aus unserer Grundmenge von
ZZSAM und die sei eben eine geeignete Menge für die ZZSAM Instanz.
Ja, was gilt dann?
Ja gut, dann ist diese Summe Y aus S', wie von Y gerade dem K, was
definiert ist als Summe X gleich 0 bis M minus 1, P hoch X.
Und das heißt aber, jedes X aus X kommt genau in einem dieser Y aus S'
vor.
Das heißt also, genau diese Menge ist, die eine Lösung ist für ZZSAM,
ist auch eine Lösung für die entsprechende XSectCover Instanz.
Also das ist trivial jetzt sozusagen.
Wir verifizieren ja Instanzen, werden genau auf ja Instanzen
abgewiesen.
Okay, wie geht es weiter?
Ja, es geht jetzt so weiter, dass wir eben für ein weiteres Problem
über Mengen zeigen, ist irgendwie vollständig.
Da ist der Beweis jetzt ziemlich einfach.
Das Problem heißt Partition.
Wir haben gegeben eine endliche Grundmenge und Gewichte auf der
Grundmenge.
Funktion auf dieser Menge, also jedem Element der Menge wird wieder
eine natürliche Zahl als Gewicht zugeordnet.
Und wir fragen uns, gibt es eine Teilmenge der Grundmenge, Teilmenge
M' aus M, so dass die Gewichte der Elemente aus M' aufsummiert, genau
dasselbe ergibt, wie die Gewichte der Elemente, die nicht in M' sind.
Also in M ohne M' sind, aufsummiert.
Wenn wir das haben, dann heißt das insbesondere die Gewichte aus M'.
Das Gesamtgewicht von M' ist genau Hälfte des Gesamtgewichts von M.
Wir machen irgendwie eine Teilmenge finden in M, deren Gesamtgewicht
genau die Hälfte des Gesamtgewichts von M darstellt.
Das klingt auch wieder irgendwie ziemlich einfach.
Ist aber NP vollständig und das kann man leicht zeigen.
Erstmal, dieses Problem ist in NP.
Wenn ich Ihnen jetzt einfach so eine Menge M' zuwerfe, Teilmenge aus
M, können Sie leicht verifizieren, dass das Gesamtgewicht von dem M'
genau die Hälfte des Gesamtgewichts von M ist.
Und die polynomiale Transformation ist von Subsetsum.
Also wir reduzieren Partition auf Subsetsum in anderen Worten.
Das heißt, wir geben eine polynomiale Transformation an, die jeder
Instanz von Subsetsum, der Instanz von Partition zuordnet, sodass die
Ja -Instanzen von Subsetsum genau Ja-Instanzen von Partition
zugeordnet werden.
Dafür nehmen wir also eine Instanz von Subsetsum, die besteht aus
einer Grundmenge M, einer Gewichtsfunktion W und so einem Parameter K.
Bei Subsetsum wollten wir wissen, gibt es ein M' aus M, sodass die
Gewichte aus M' aufsummiert genau das K treffen.
Das ist ja fast dasselbe Problem wie Partition.
Wie konstruieren wir die Partition-Instanz?
Die Grundmenge ist M-Stern, die Gewichtsfunktion ist W-Stern, aber die
unterscheiden sich beide gar nicht so sehr von dem hier.
Wir berechnen erstmal die Summe der Gewichte aus M, der Elemente aus M
und nehmen diese Summe plus 1 als N, also definieren das als N.
Und M-Stern ist nichts anderes als diese Grundmenge M von Subsetsum
plus zwei weitere Elemente B und C.
Und die Gewichtsfunktion auf M-Stern ist so, die Gewichte der Elemente
aus M kriegen ihre alten Gewichte, wie sie sie bei Subsetsum hatten.
Also W-Stern von A ist W von A, wenn A in M war.
Und für die zwei zusätzlichen Elemente, die wir hier zu M-Stern dazu
gesteckt haben, B und C, wählen wir jetzt noch geeignete Gewichte.
Und zwar definieren wir das Gewicht von B als N minus K.
K ist dieser Parameter hier und N ist ja Gewichte der Elemente aus M
aufsummiert plus 1.
Und Gewicht von C definieren wir als K plus 1.
Also wenn wir die beiden Gewichte B und C aufsummieren würden, dann
bekämen wir wieder gerade das Gewicht von M raus.
Also N ist Gewicht von M plus 1 minus K und K minus K und Gewicht von
C ist K plus 1.
Das heißt, wenn wir die beiden Gewichte aufsummieren würden, dann
bekämen wir gerade diese Summe raus.
Das sieht ja irgendwie praktisch aus, denn daraus folgt gleich unsere
Behauptung, dass Jahrinstanzen in Jahrinstanzen abgebildet werden.
Erstmal vorneweg, die Konstruktion ist natürlich polynomial.
Wieso ist das so, dass eine Jahrinstanz von Subsetsum, Instanz M, W, K
genau auf eine Jahrinstanz von Partition, Instanz M-Stern, W-Stern,
abgebildet wird und umgekehrt?
Also wieso ist M, W, K eine Jahrinstanz genau dann, wenn die
entsprechende Instanz M-Stern, W-Stern eine Jahrinstanz ist?
Na gut, das ist eine Jahrinstanz, wenn so ein M-Strich aus...
Das hier ist eine Jahrinstanz, wenn es so ein M-Strich aus M-Stern
gibt mit Gewichte aus M-Strich aufsummiert, ist es dasselbe wie die
Gewichte aus M-Stern ohne M-Strich aufsummiert.
Das ist aber nichts anderes, wie wir nehmen eine Teilmenge von M,
deren Gewicht genau K ergibt.
Denn, erstmal wenn wir so ein M-Strich aus M-Stern betrachten, für das
gilt, das enthält gerade die Hälfte des Gewichtes von M-Stern, dann
können die beiden Extra-Elemente B und C nicht beide auf derselben
Seite liegen.
Die können nicht beide in M-Strich sein.
Die können auch nicht beide in M-Stern ohne M-Strich sein.
Das ist einfach zu viel, weil die einfach zu viel Gesamtgewicht haben,
die beiden zusammen.
Wenn wir so eine Jahrinstanz von Partition betrachten, dann halten B
und C nicht beide in der Lösung.
Dann folgt, da ja für M-Strich gilt, dass die Summe der Gewichte der
Elemente aus M-Strich bezüglich W-Stern gleich dasselbe wie die Summe
der Gewichte der Elemente aus M-Stern ohne M-Strich bezüglich W-Stern
ist, dass das Gewicht von M-Strich gerade N ist.
Denn das M-Stern hat insgesamt gerade Gewicht 2N.
So ist N definiert und das Gewicht von B und C definiert.
Dann können wir aber gerade M-Strich ohne B hernehmen und haben damit
unsere Menge M-2-Strich, die Lösung von Subset-Sum ist.
Und bei der Rückrichtung ist genauso, wenn wir für Subset-Sum so ein M
-Strich haben, dessen Gewicht K ist, dann brauchen wir einfach nur das
B noch dazu zu stecken und haben dann eine Menge M-Strich, deren
Gewicht gerade erfüllt.
Gewicht von M-Strich ist gleich Gewicht von M-Stern ohne M-Strich.
Gut, also das war jetzt auch ziemlich einfach.
Und jetzt eben das letzte Problem, für das wir heute zeigen, dass es
NP -Vollständig ist, Knapsack.
Und jetzt dieser NP-Vollständigkeitsbeweis von Partition hatte vor
allem den Zweck, dass wir sozusagen jetzt das richtige Problem haben,
um für Knapsack zu beweisen, dass es NP-Vollständig ist.
Und Knapsack ist, wie ich eben schon angekündigt habe, insofern ein
interessantes Problem, als dass das unter den NP-Vollständigen
Problemen eines ist, was irgendwie in gewisser Weise einfacher ist als
andere.
Denn, wie wir später sehen werden, kann man dafür einen Algorithmus
entwerfen, der auf den ersten Blick polynomial aussieht.
Wenn man genauer hinguckt, ist er nicht wirklich polynomial, weil die
Gewichte, die in der Problemstellung vorkommen, in dem entsprechenden
Lösungsalgorithmus nicht, wie wir es fordern, nur logarithmisch
eingehen, sondern tatsächlich in ihrer Größe eingehen.
Das ist dann wieder nicht mehr polynomial in dem, was wir als eine
sinnvolle Codierung, Codierungslänge unserer Eingabeinstanzen ansehen,
weil wir ja Gewichte, also solche Zahlenwerte, mit denen gerechnet
wird, so dass die Länge logarithmisch ist.
Da dürfen die Gewichte dann nicht als Ganzes in die Laufzeit eingehen.
Aber solche Algorithmen, die nennt man pseudopolynomial, die sind also
sozusagen fast polynomial.
Und für Knapsack gibt es eben so einen pseudopolynomialen Algorithmus,
also insofern spielt Knapsack unter den NP-Vollständigen Problemen,
die wir hier kennenlernen, eine besondere Rolle.
Knapsack ist aber auch interessant, weil das das typische Problem für
Nikolaus ist.
Das ist nämlich das Problem, das der Weihnachtsmann oder Nikolaus
lösen muss.
Denn worum geht's?
Also Knapsack steht für Rucksack.
Es geht darum, dass Nikolaus sozusagen seinen Rucksack mit Geschenken
besonders geschickt wählt.
Denn Knapsack ist definiert als gegeben eine Grundmenge M.
Können Sie sich vorstellen als Menge von Geschenken.
Die Elemente aus M haben einerseits ein Gewicht, entspricht also
wirklich dem Gewicht von Dingen und andererseits Kosten oder einen
Wert.
Und dann haben wir noch so ein Maximalgewicht Groß W und so ein
Parameter für einen Wert, den wir auf jeden Fall erzielen wollen, C.
Also gegeben ist eine Grundmenge, eine Gewichtsfunktion auf der
Grundmenge, eine Kostenfunktion oder Wertefunktion auf der Grundmenge
und so ein Parameter Groß W und ein Parameter Groß C.
Und die Frage ist, existiert eine Teilmenge M' aus M, sodass das
Gesamtgewicht dieser Teilmenge M', also aufsummiert die Gewichte der
Elemente A aus M', kleiner gleich Groß W ist.
Und dass andererseits die Kosten der Elemente aus M' aufsummiert
mindestens Groß C ist.
Warum ist das das Problem, das der Nikolaus lösen muss?
Naja, er soll unter den ganzen Geschenken einpacken,
Teilmenge, die er noch tragen kann, deren Gesamtgewicht, also kleiner
gleich dem Maximalgewicht ist, das er tragen kann, die aber möglichst
wertvoll sind.
Das heißt, deren Gesamtwert größer gleich so einem vorgegebenen Wert C
ist.
Wenn man das jetzt übersetzt in ein Optimierungsproblem, dann wäre das
Optimierungsproblem, also maximiere den Wert Summe A aus M' C von A.
Mache das möglichst groß unter der Nebenbedingung, dass das
Gesamtgewicht dieser Menge von Elementen kleiner gleich dem
Maximalgewicht ist, was der Nikolaus tragen kann.
So, das Problem ist leider NP vollständig.
Dass es in NP ist, ist offensichtlich.
Ja, wir können wieder für so eine Menge M' leicht verifizieren, dass
deren Gesamtgewicht kleiner gleich W ist und dass deren Gesamtwert
größer gleich C ist.
Und man kann sich leicht überlegen, dass sich Partition polynomial in
Knapsack transformieren lässt.
Nehmen uns einfach eine Instanz von Partition her.
Die zugehörige Instanz von Knapsack sieht folgendermaßen aus.
Wir nehmen dieselbe Menge M.
Die Gewichtsfunktion ist leicht modifiziert.
Wir definieren noch eine Kostenfunktion und wir müssen so ein W und so
ein C definieren.
Und die Gewichtsfunktion ist die, wir nehmen einfach für jedes Element
als Gewichtsfunktion W' bezüglich Knapsack zweimal das Gewicht, das
das Element bezüglich Partition hat.
Und die Kostenfunktion ist genauso definiert.
Die Kosten eines Elementes sind zweimal dem Gewicht des Elementes in
der entsprechenden Partition Instanz.
Und diese Threshold oder dieses Maximalgewicht W und die Minimalkosten
C sind gleich gewählt.
Das ist einfach die Gewichte der Elemente der Grundmenge aufsummiert.
Gewichte bezüglich der Partition Instanz.
Das kann man in Polynomialzeit konstruieren und es ist leicht
einzusehen, dass so eine Instanz Mw eine Ja-Instanz für Partition ist,
genau dann, wenn die konstruierte Instanz für Knapsack eine Ja-Instanz
für Knapsack ist.
Das machen wir jetzt nicht mehr zu Fuß.
Offensichtlich können Sie es selber überlegen.
Okay.
So, damit werden wir mit unseren NP-Vollständigkeitsbeweisen für die
Vorlesung durch.
In der Übung werden Sie sicher noch einige führen.
Was jetzt?
Bisher haben wir nur definiert, wie die Klassen P und NP aussehen.
Und jetzt, wie sieht die Welt um diese Klassen herum aus?
Also die große Frage ist ja, ob P ungleich NP ist oder gleich.
Ja, was haben wir gesehen?
Wir haben für zwei NP-Vollständige Probleme gesehen, dass es eine
polynomiale Transformation von dem einen auf das andere gibt.
Erstmal in dem, per Beweis haben wir für immer für ein Problem, für
das wir erst gezeigt haben, ist NP-Vollständig eines hergenommen, von
dem wir wissen, dass es NP-Vollständig ist, eine polynomiale
Transformation von diesem bekannten NP-Vollständigen zu dem neuen
angegeben.
Nachdem das passiert ist, wissen wir nach Definition von NP
-Vollständigkeit, dass wir von diesem neuen NP-Vollständigen Problem
auf jeden Fall eine polynomiale Transformation zu jedem anderen NP
-Vollständigen Problem haben.
Insofern ist, wenn wir zwei NP-Vollständige haben, das eine können wir
in das andere überführen und umgekehrt.
Durch eine Polynomiale.
Das heißt also, bezüglich dieser polynomialen Transformierbarkeit sind
alle NP-Vollständigen Probleme gleich schwer.
Bezüglich anderem, was auch mit algorithmischer Effizienz, effizienter
Lösbarkeit zu tun hat oder guter Lösbarkeit, sind die durchaus
unterschiedlich schwer.
So wie auch für Probleme aus P gilt.
Das eine haben wir vielleicht einen Lösungsalgorithmus, der Linearzeit
hat und beim anderen das Beste, was man erzielen kann, vielleicht nur
kubisch.
Obwohl alle Probleme, die in P liegen, sind trotzdem in gewisser Weise
bezüglich algorithmischer, effizienter Lösbarkeit wieder
unterschiedlich schwer.
Und so haben wir natürlich in NP eben einerseits dieses NP
-Vollständige Probleme sind bezüglich polynomialer Transformierbarkeit
gleich schwer.
Bezüglich anderem, was wir noch betrachten werden, können wir durchaus
differenzieren.
Das hat aber, dass sie bezüglich polynomialer Transformierbarkeit
gleich schwer sind, Auswirkungen auf diese Frage, ob P gleich NP ist.
Das sagt uns der folgende Satz.
Denn wenn wir ein NP-Vollständiges Problem haben, und für dieses
zeigen können, es liegt in P, dann haben wir automatisch P gleich NP
bewiesen.
Und andererseits, wenn wir für dieses zeigen können, es liegt nicht in
P, dann haben wir automatisch bewiesen, dass sämtliche NP
-Vollständigen Probleme nicht in P liegen.
Wenn wir gleich nochmal genauer uns überlegen, wieso das so ist.
Aber ich formuliere den Satz jetzt nochmal für Sprachen, denn wir
werden die meisten Dinge, wie wir es bisher auch gemacht haben, wenn
wir wirklich ans Beweisen gehen, eben für Sprachen beweisen.
Also sei L eine NP-Vollständige Sprache, dann gelten zwei Dinge.
Das erste, wenn L auch in P liegt, dann ist P gleich NP.
Und zweitens, wenn L nicht in P liegt, dann gilt für jede NP
-Vollständige Sprache L' dass sie auch nicht in P liegt.
Beweis für den ersten Teil.
Also L sei NP-Vollständig und L sei in P. Folgt P gleich NP.
Wieso?
Also nehmen wir mal so eine Sprache aus P her, die gleichzeitig NP
-Vollständig ist.
Weil die Sprache in P ist, existiert eine polynomiale deterministische
Turing -Maschine, die die Sprache L entscheidet.
Und jetzt sei L irgendeine andere Sprache aus NP.
Um zu zeigen, dass P gleich NP ist, müssen wir für eine beliebige
andere Sprache aus L' aus NP zeigen können, sie liegt auch in P. Dafür
nehmen wir das L' hier.
Weil L NP-Vollständig ist, können wir L' polynomial transformieren auf
L.
Dann können wir aber mit den beiden zusammen, den beiden Sachen
zusammen, der polynomial deterministischen Turing-Maschine für L,
zusammen mit der polynomialen Transformation L' auf L, auch eine
polynomial deterministische Turing-Maschine für L' angeben.
Polynomial deterministische Turing-Maschine für L', das heißt einfach,
wir haben eine polynomial deterministische Turing-Maschine, um L' zu
entscheiden, um für irgendeine Eingabe, irgendein Wort zu entscheiden,
ist das Wort in L' oder nicht.
Wie machen wir das?
Wir bauen erstmal zu dem Wort aus, für das wir das entscheiden wollen,
mit der polynomialen Transformation, die wir hier haben, ein Wort, für
das wir dann mit der polynomial deterministischen Turing-Maschine für
L' entscheiden, ob das Wort in L' ist.
Da Worte aus L' genau auf die Worte aus L' abgebildet werden, können
wir damit also auch für unseren Ausgangswort entscheiden, ob es in L'
war.
Und alles, was wir gemacht haben, war polynomial.
Das heißt, wir haben dann damit, durch die Hintereinanderausführung
der polynomialen Transformation und der polynomial deterministischen
Turing -Maschine auch eine polynomial deterministische Turing-Maschine
für L'.
Das heißt also, für unsere beliebige Sprache L' aus NP haben wir
gezeigt, sie ist in P. Damit haben wir die erste Behauptung des Satzes
bewiesen, dass wenn wir eine NP-vollständige Sprache haben und für die
zeigen können, sie ist in NP, dass dann P gleich NP ist.
Für die zweite Aussage, dass wenn wir eine NP-vollständige Sprache
haben und für die zeigen können, sie ist nicht in P, dass dann
sämtliche NP-vollständigen Sprachen nicht in P sind.
Schauen wir uns also so eine NP-vollständige Sprache L' an, die nicht
in P ist.
So, und jetzt gucken wir uns eine beliebige andere NP-vollständige
Sprache L' an und nehmen mal an, die wäre aber in P. Dann folgt aber
mit dem ersten Teil des Satzes, den wir gerade bewiesen haben, dass P
gleich NP ist.
Unter Benutzung von L' für die Aussage.
Und dann hätten wir sofort den Widerspruch zu der Annahme, dass aber
unsere NP-vollständige Ausgangssprache L' nicht in P ist.
Das heißt also, der zweite Teil des Satzes, ich gehe nochmal zurück
auf den Satz, dieser zweite Teil folgt unmittelbar aus dem ersten
Teil.
Das waren jetzt keine schwierigen Argumente, diesen Satz zu beweisen.
Aber in dem Satz steckt sozusagen drin,
die Bedeutung von NP-vollständigen Problemen für die Frage, ob P
ungleich NP ist.
Denn wenn Sie beweisen wollen, dass P gleich NP ist, müssten Sie
einfach nur für ein NP-vollständiges Problem einen polynomialen
Algorithmus angehen.
Einfach einen polynomialen Algorithmus für drei Satz und dann ist
schon alles erledigt.
Andererseits, wenn Sie beweisen wollen, P ist ungleich NP, dann
müssten Sie also für irgendein NP-vollständiges Problem zeigen, das
kann nicht in polynomialzeitdeterministisch gelöst werden.
Dann haben Sie automatisch, dass alle NP-vollständigen Probleme
außerhalb von P liegen.
Dann haben Sie automatisch die Differenzierung.
So, Zusammenfassung jetzt erstmal für den Moment.
Also wir haben die Klasse P, Klasse der deterministischen
Entscheidungen, also Klasse der Entscheidungsprobleme, die sich mit
einer deterministischen Turing-Maschine in polynomialer Zeit lösen
lassen und die Klasse NP, die Klasse aller Entscheidungsprobleme, die
sich mit einer nicht-deterministischen Turing-Maschine in polynomialer
Zeit lösen lassen.
Und noch mal informell ausgedrückt, so ein Problem, so ein
Entscheidungsproblem gehört zur NP.
Falls gilt, ist die Antwort bei Eingabe eines Beispiels oder einer
Instanz von Pi ja, dann kann die Korrektheit dafür in polynomialer
Zeit überprüft werden, die Korrektheit eines Zeugen, der das belegt.
Und weiter, der Begriff der NP-Vollständigkeit basiert auf dem Begriff
der polynomialen Transformation, also eine Sprache L1 kann polynomial
in eine Sprache L2 transformiert werden, wenn man eine Funktion haben,
die Worte über dem Alphabet von L1 auf Worte über dem Alphabet von L2
abbildet und folgende Eigenschaften hat.
Erstmal die Funktion lässt sich durch eine polynomiale
deterministische Turing-Maschine berechnen und zweitens die Worte aus
L1 werden genau auf Worte aus L2 abgebildet.
Und NP-Vollständig heißt eben eine Sprache, wenn sie in NP ist und
sich alle anderen Sprachen aus NP polynomiell transformieren lassen.
Und wenn man jetzt also annehmt, das was die Mehrheit glaubt, dass P
ungleich NP ist, dann gibt es also für ein NP-Vollständiges Problem
kein polynomiales Lösungsverfahren.
Das ist sozusagen der Knackpunkt.
Wir haben den Satz von Cook bewiesen, dass Sat NP schwer ist und dann
haben wir eine ganze Menge von polynomialen Transformationen oder
Reduktionen durchgeführt von Sat auf Drei-Sat und so weiter.
Wie geht die Story weiter?
Also wie gesagt, wir haben jetzt nur NP und P und gibt es überhaupt in
dieser Welt NP und da drin liegt P noch Probleme, die weder in P sind,
noch NP-Vollständig sind.
Nennen wir mal die Menge der NP-Vollständigen Probleme NPC, die
Teilmenge aus NP NP-Vollständig sind, NP-Complete, NPC für NP
-Complete.
Dann können wir auch NP ohne P-Vereinigt NPC mal angucken.
Also wir nehmen in NP, wir nehmen NP, nehmen die Probleme aus P raus
und nehmen die NP-Vollständigen raus.
Frage, bleibt da überhaupt was übrig?
Wir nennen mal die Klasse der Probleme, die da übrig bleibt NP-I, I
für Intermediate.
So, das ist jetzt mal das allererste, was man sich fragen kann, bleibt
da überhaupt was übrig?
Gibt es Probleme in NP-I?
Und dann ist noch ganz interessant, folgendes zu machen.
Zu Sprachen oder Problemen aus P oder NP, die Komplementsprachen
betrachten.
Welche Komplementprobleme?
Also, ich habe eine Sprache L in P, die lebt über dem Alphabet Sigma.
Also die Worte aus L sind die Worte aus Sigma-Stern, die in L sind und
die restlichen, das Komplement der Sprache, ist halt Sigma-Stern ohne
L.
Und diese Sprachen, die gucke ich jetzt mal an, zu Sprachen L aus P.
Und die Klasse dieser Sprachen, die nenne ich CoP.
Die Klasse der Komplementsprachen von Sprachen aus P. Ich mache hier
extra langsam, weil
es sich so naheliegend ist, hier was anderes zu vermuten.
Ich sage nicht was.
Also CoP ist die Menge der Komplementsprachen von Sprachen aus P. Und
Komplementsprache ist einfach zu einer Sprache die Sprache der Wörter
über dem entsprechenden Alphabet, die nicht in der Sprache ist.
Und dasselbe kannst du natürlich auch für NP-Sprachen machen.
Also CoNP ist die Klasse aller Sprachen, steht hier explizit Sigma
-Stern ohne L, für L in Sigma-Stern und L in NP.
Also die Komplementsprachen zu Sprachen aus NP.
Das sieht jetzt harmlos aus, wir werden gleich aber sehen, dass die da
vielleicht doch nicht so harmlos sind, die Sprachen, die da landen.
Erstmal zu diesem ersten Teil.
Es ist tatsächlich bewiesen worden 1975, dass falls P ungleich NP ist,
NPI ungleich leer ist.
Also dann gibt es innerhalb von NP noch Probleme, die weder NP sind,
noch NP-vollständig sind.
Beweisen wir hier nicht.
So, das Bild ist so, also NP, da drin liegt P, da drin liegt NPC, also
NPC die schwersten in NP, die NP-vollständig, NP-complete und nach
diesem Satz von Lettner ist es so, also wenn wirklich P ungleich NP
ist, also die hier wirklich hier außerhalb von P liegen, dann gibt es
noch andere, da gibt es hier noch Probleme.
Da gibt es, dann ist NPI ungleich leer.
So und jetzt, wie ist das mit CoP und CoNP?
Also erstmal, eins ist ja offensichtlich, die Menge der
Komplementsprachen von Sprachen in P ist wieder P. Eine Sprache ist in
P, wenn es eine deterministische Turing-Maschine gibt, die in
Polynomialzeit diese Sprache entscheiden kann.
Alles deterministisch, das heißt, die kann genauso mit genau demselben
Mechanismus, genau derselben Turing-Maschine kann man dann in
Polynomialzeit auch das Komplement der Sprache entscheiden.
Sprache entscheiden heißt ja nur, ich gebe ein Wort ein und die
deterministische Turing-Maschine sagt mir nach polynomialer Zeit, das
Wort ist in der Sprache oder das Wort ist nicht in der Sprache.
Damit wird die Sprache entschieden und damit wird auch deren
Komplement entschieden.
Also P und QP sind gleich.
Was ist mit NP und QNP?
Was ist das Komplement einer Sprache, die in NP liegt?
Werden wir gleich sehen, dass das da nicht so klar ist, was das
eigentlich heißt, das Komplement einer Sprache aus NP zu entscheiden.
Aber wir haben zwar P gleich Q NP, aber wie ist das eigentlich mit NP
und QNP?
Sind NP und QNP auch gleich?
Also die erste Frage.
Wenn die nicht gleich wären, wenn NP und QNP verschieden sind, dann
ist auch klar, dass P ungleich NP ist.
Es kann nicht gleichzeitig NP ungleich QNP, aber P gleich QP sein.
Egal.
Wenn NP gleich QNP ist, kann man daraus nicht automatisch P gleich NP
folgern.
Also irgendwie so Fragezeichen, was würde daraus folgern?
Also, wie schon gesagt, erstmal die große Vermutung ist, P ungleich
NP.
Ich kenne niemanden, der an P gleich NP glaubt.
Und es vermuten auch mindestens so viele Leute, dass NP ungleich QNP
ist.
Das ist sozusagen eine weitreichendere Vermutung.
So, und jetzt gucken wir uns mal tatsächlich QNP an.
Also wir nehmen uns ein Problem aus NP vor, am besten sogar ein NP
-Vollständiges, und schauen mal, was ist denn dessen
Komplementproblem?
Also beim Problem ist es ja so, wenn man das in Sprachen übersetzt,
die Sprache zu einem Problem ist ja die Menge der Codierungen der Ja
-Instanzen.
Das heißt also, das Komplement des Problems ist die Menge der
Codierungen der Nein-Instanzen.
Jetzt gucken wir uns Travelling Salesman an.
Travelling Salesman ist das Problem.
Wir haben gegeben einen vollständigen Graph mit einer
Kantengewichtsfunktion, und wir haben vorgegeben einen Parameter K,
und die Frage ist, gibt es eine Tour über alle Knoten des Graph, wo
die jeden Knoten des Graph genau einmal durchläuft, deren
Gesamtgewicht kleiner gleich K ist.
Ja-Instanz ist eben eine, wo es so was gibt.
Komplement von den Ja-Instanzen sind all die Instanzen, wo es sowas
nicht gibt.
Das heißt also, QTSP ist gegeben, ein Graph, vollständiger Graph mit
Kantengewichtsfunktion und Parameter K, gibt es keine Tour über der
Länge kleiner gleich K.
Und wenn Sie jetzt mal an polynomielle Entscheidbarkeit mit einer
nichtdeterministischen Turing-Maschine denken und sich überlegen, gibt
es sowas hierfür?
Dann stehen Sie wahrscheinlich genau wie ich jetzt im Moment ratlos
da, um sozusagen für TSP mit einer polynomialen Turing-Maschine eine
Lösung zu generieren, also eine sozusagen eine Berechnung anzugeben,
die eine Ja-Instanz entscheidet, müssen Sie einfach nur für eine
Instanz, eine Ja-Instanz in Polynomialzeit für eine einfach
vorgegebene Tour nachprüfen.
Die Tour hat eine Länge kleiner gleich K.
Jetzt für so eine Ja-Instanz von QTSP ein Beleg für, es gibt keine
Tour der Länge kleiner gleich K in Polynomialzeit überprüfen.
Jo.
Also für ein vernünftiges Codierungsschema ist leicht nachzuweisen, ob
sozusagen eine TSP-Instanz eine Ja-Instanz ist, aber für eine QTSP-
Instanz zu entscheiden, ob es eine Ja-Instanz ist, wissen wir nicht.
QTSP ist in QNP, weil TSP in NP ist.
Wozu wir gerade achselzuckend festgestellt haben, wir wissen es nicht,
war die Frage, ist QTSP auch in NP?
Und die Vermutung ist eben, nein.
Die Vermutung ist, diese NP-vollständigen Probleme, für die gilt,
deren Komplementprobleme liegen nicht in NP.
Jetzt gilt, wenn L NP vollständig ist und gleichzeitig in QNP, dann
ist NP gleich QNP.
Das können wir uns wieder leicht überlegen.
Also sei L in QNP einerseits und NP vollständig andererseits.
Wir haben eine NP-vollständige Sprache L, die in QNP liegt.
Weil L in QNP liegt, existiert eine polynomiale, nicht
deterministische Berechnung für das Komplement von L.
Also für L-Komplement.
Und andererseits, weil L NP vollständig ist, gilt für alle Sprachen L'
aus NP.
L' ist polynomial transformierbar auf L.
Dann haben wir aber auch eine deterministische polynomiale
Transformation von L'-Komplement zu L-Komplement.
Denn das hier heißt ja einfach, wir haben so eine Funktion, die uns
Instanzen, also Wörter über dem Alphabet von L' auf Wörter über dem
Alphabet von L abbildet, sodass die Wörter aus L' genau auf Wörter auf
L' abgebildet werden.
Also Wörter, die in L'-Komplement sind, genau auf Wörter, die in L'
-Komplement sind.
Das heißt also, diese polynomiale Transformation von L' auf L', die
können wir auch genauso verwenden als polynomiale Transformation von
L' -Komplement auf L'-Komplement.
So.
Deshalb existiert also, wenn wir das kombinieren mit der polynomial
nicht -deterministischen Berechnung für L'-Komplement, auch eine
polynomiale nicht-deterministische Berechnung für L'-Komplement.
So einen Schritt haben wir schon mal öfter gemacht.
Also wenn wir haben, wir können das polynomial transformieren darauf
und das ist in NP, dann ist auch das hier in NP.
Was aber automatisch heißt, dass dann L'-Komplement Komplement, was ja
L' ist, in QNP ist.
Damit haben wir den Satz bewiesen.
Also wenn wir für ein NP-vollständiges Problem zeigen können, es ist
auch gleichzeitig in QNP, dann ist NP gleich QNP.
Aber wie bei TSP
gesehen, scheint das für so ein NP-vollständiges Problem nicht so
offensichtlich zu sein.
Zumindest bei TSP glauben wir eher, das ist nicht der Fall, dass QTSP
in QNP ist.
Mit der Vermutung, also dass NP ungleich QNP ist, folgt auch, dass der
Durchschnitt zwischen QNP und der Klasse der NP-vollständigen Probleme
leer ist.
Also das hier folgt unmittelbar aus dem Satz, den wir gerade bewiesen
haben.
Und daraus kann man jetzt ableiten, eine Beziehung zwischen NP-QNP
einerseits und NPI, nämlich, wenn ein Problem in NP und in QNP liegt,
aber nicht in P, dann muss es in NPI sein.
NP-vollständig kann es nach dem hier nicht sein.
Das heißt also, für unsere NP-Intermediate, also die Probleme, die
zwar in NP liegen, aber weder in P, noch NP-vollständig sind, von
denen wir bisher jetzt noch kein einziges kennengelernt haben, die
haben auch mit QNP zu tun, nämlich das scheinen genau die zu sein, die
in NP-Schnitt QNP ohne P sind.
So, und jetzt will ich Ihnen einen Kandidaten für NPI vorstellen.
Dazu fangen wir jetzt mit einem schwierigeren Problem an, was NP
-vollständig ist, nämlich dem Subgraf- Isomorphie-Problem.
Sie haben gegeben einen großen Graf G und ich sag mal einen kleineren
Graf H.
Also G besteht aus der Knotenmenge V und der Kantenmenge E und H steht
aus der Knotenmenge V' und der Kantenmenge E' und das V' ist kleiner
als das V.
In dem Sinne ist das ein kleinerer Graf.
Und jetzt ist die Frage, gibt es in G einen Subgraf, der genauso
aussieht wie H?
Gibt es in G einen knoteninduzierten Subgraf, der isomorph ist zu?
In anderen Worten, gibt es eine Teilmenge der Knotenmenge von G, die
genauso viele Knoten enthält wie H, also Teilmenge U aus V
Kardinalität von U ist gleich Kardinalität von V' und gibt es eine
bijektive Abbildung von V' nach U, sodass für je zwei Knoten XY aus V'
gilt, wenn XY durch eine Kante verbunden sind in H, dann sind die
Bilder von XY durch eine Kante verbunden in G und umgekehrt.
Also der durch U induzierte Teilgraf von G sieht genauso aus wie H.
Das Problem ist NP-vollständig?
Verweisen wir nicht.
Und jetzt kann man das ein bisschen vereinfachen, indem man einfach
sagt, G und H sind gleich groß.
Dann ist die Frage, einfach, die sind G und H isomorph.
Also gegeben G gleich V E und H gleich V' E' Flächigkeit V gleich
Mächtigkeit V'.
Existiert eine bijektive Abbildung von der Knotenmenge V' nach V,
sodass Kanten aus H auf Kanten aus G abgebildet werden und umgekehrt.
Also sind G und H isomorph.
Sehen die eigentlich von der Struktur ja genau gleich aus.
Und dieses Problem ist ein Kandidat für NPI.
Das wurde dann später bewiesen, dass wenn P ungleich NP ist, dann ist
ja NPI ungleich leer.
Das ist dann Grafisomorphie in NPI.
Und Grafisomorphie liegt tatsächlich in NP und QNP.
Das ist offensichtlich, dass hier wieder das Komplementproblem
dasselbe ist.
Sind die isomorph?
Sind die nicht isomorph?
Also zwei Grafen gegeben.
Frage, sind die isomorph?
Das ist Grafisomorphie.
Komplement von Grafisomorphie wäre zwei Grafen gegeben.
Frage, sind die nicht isomorph?
Also die Welt sieht wohl so aus.
Hier habe ich NP.
Hier habe ich P. Hier habe ich NP vollständig.
Dann gibt es da NPI irgendwie.
Und hier ist QNP.
Also wir vermuten ja, QNP ist ungleich P. Auf jeden Fall liegt P im
Durchschnitt von QNP und NP.
Ja, der Durchschnitt von den beiden ist nicht leer, weil P liegt auf
jeden Fall drin.
Und da liegen also noch die NPI Probleme drin.
Ich will Ihnen jetzt mal erst noch was zeigen.
Es gibt eine schöne Webseite zu P versus NP.
Da ist alles Mögliche aufgeführt.
Brauchbare Literatur, wie
Paper von Steven Kopp zu dem Thema.
Wikipedia-Seiten und so weiter.
Interessante Paper zum Beispiel von Christoph Papidimitriou über NP
-Vollständigkeit.
So ein bisschen.
Okay, das sind schon mal interessante Literaturhinweise.
Ein Paper, was zum Beispiel berichtet über eine Meinungsumfrage zu P
versus NP.
Wie viele glauben, P gleich NP?
Wie viele glauben, P ist ungleich NP?
Okay.
Und hier Milestones.
Das darf man nicht alles jetzt so ganz ernst nehmen.
Ich habe Ihnen mal anfangs, als wir mit dem Kapitel angefangen haben,
gesagt, so über die Historie, seit dem Satz von Cook, seit er bewiesen
wurde, sind immer mal wieder Leute hingegangen und haben gesagt, ich
habe jetzt bewiesen, P gleich NP.
Und auch andere, die gesagt haben, ich habe jetzt bewiesen, P ungleich
NP.
Mittlerweile wissen wir, wie so ein Beweis laufen könnte.
Für P gleich NP würde man einfach für ein NP-Vollständiges Problem
zeigen, es gibt einen polynomialen Algorithmus.
Also einfach für TSP oder Subgraphisomorphie einen polynomialen
Algorithmus angeben.
Um zu zeigen, P ungleich NP für irgendeins dieser NP-Vollständigen
Probleme zeigen, es kann keinen polynomialen Algorithmus geben.
Hier ist also aufgelistet eine ganze Menge von Veröffentlichungen, in
Anführungszeichen, die equal or not equal, also Gleichheit oder
Ungleichheit von P und NP beweisen.
Da gibt es noch ein paar andere Sachen dazwischen, wie zum Beispiel
der Versuch zu zeigen, das kann man nicht beweisen, ob P gleich NP
oder P ungleich NP ist.
Das ist ein unentscheidbares Problem.
Zu all diesen Veröffentlichungen ist anzumerken, keine ist rigoros
begutachtet und für okay befunden worden.
Und da gibt es so ein paar Wiederholungstäter, die immer wieder
beweisen, P ungleich NP.
Nicht so richtig mit Erfolg.
Also, wenn Sie mal ein bisschen Spaß haben wollen, gucken Sie sich das
an.
Ich selber habe im Laufe meines Lebens auch immer mal wieder Beweise
für P gleich NP begutachten dürfen.
Gut, dann versucht mal den Fehler zu finden.
Dass der Algorithmus doch nicht polynomial ist.
Ein ganz häufiger Weg P gleich NP zu beweisen ist einer, den wir erst
dann ganz in der nächsten Vorlesung verstehen werden, nämlich für ein
NP -vollständiges Problem ein sogenanntes lineares Programm anzugeben,
das nur polynomiale Größe hat und dann hat man den polynomialen
Algorithmus automatisch und da war dann immer das Problem, dass das
dann, wenn man genauer hinguckt, doch nicht polynomial Größe hat.
Also, das zu dem zur Historie von P ungleich NP und jetzt noch für die
letzten 20 Minuten heute so ein kleiner Exkurs zu Problemen, die von
ihrer Formulierung her eben nicht so aussehen wie
Entscheidungsprobleme, denn wir werden ja dann später, spätestens wenn
wir dann approximierende Algorithmen entwerfen, ja nicht
Entscheidungsprobleme angucken, sondern Optimierungsprobleme wie TSP
finde eine optimale Tour oder Suchprobleme, finde eine zulässige
Lösung für ein Problem einer bestimmten Art oder finde alle Lösungen
oder sag mir, wie viele Lösungen es gibt.
Und einfach wie man diese sozusagen andockt an die Theorie der NP
vollständigen Probleme, darum geht es jetzt hier.
Also, Sie können auch betrachten Suchprobleme.
Was ist ein Suchproblem?
Suchproblem ist gegeben durch eine Menge von Probleminstanzen, die
Menge nennen wir wieder DP und eine Menge von Lösungen, Menge der
Lösungen SP.
Und die Lösung eines Suchproblems ist eben einfach eine Lösung, eine
zulässige Lösung anzugeben, wenn es eine gibt oder zu sagen, es gibt
keine.
TSP Suchproblem wäre zum Beispiel folgende Formulierung, wäre ein
Suchproblem zur TSP.
Sie haben hier einen vollständigen Graph gegeben und eine
Kantengewichtsfunktion gibt mir eine optimale Tour an, eine Tour
minimaler Länge.
Es kann ja mehrere Touren minimaler Länge geben, gib mir eine davon.
Oder aber Sie haben noch so einen Parameter K gegeben und jetzt gib
mir eine Tour der Länge höchstens K, also deren Länge kleiner gleich K
ist.
Davon kann es ja auch mehrere geben und Sie wollen einfach aus dieser
Menge der Touren der Länge kleiner gleich K eine haben.
Das wäre eine Suchproblemvariante von TSP.
Nettes Problem ist Hamilton-Kreis.
Das hat so ein bisschen zu tun mit TSP.
Gegeben ein Graph.
Ein Hamilton-Kreis ist eine Tour durch den Graph, bei der jeder Knoten
genau einmal durchlaufen wird.
Das heißt also, eine Permutation der Knotenmenge so das gilt für zwei
in der Permutation aufeinander folgende Knoten habe ich auch eine
Kante.
Wenn Sie einen beliebigen Graph gegeben haben, ist nicht klar, ob es
so einen Hamilton-Kreis gibt.
Also ein relevantes Problem für einen beliebigen Graphen zu
entscheiden, gibt es einen Hamilton-Kreis?
Das Problem ist NP-Vollständig und jetzt Versuchproblem dazu, wer gibt
mir einen Hamilton-Kreis?
Also nicht nur gegeben ein Graph beantworte mir die Frage, gibt es
einen Hamilton-Kreis, sondern gegeben ein Graph, gibt mir einen
Hamilton -Kreis, wenn es einen gibt.
Und dann könnten Sie aber auch das Aufzählungsproblem dazu
formulieren.
Allgemeinaufzählungsproblem P, Sie haben wieder das Problem gegeben
durch die Menge der Probleminstanzen und Sie haben die Menge aller
zulässigen Lösungen gegeben und beim Aufzählungsproblem wollen Sie
wissen, wie viele gibt es?
Wie viele Lösungen gibt es?
Das wäre jetzt bei Hamilton-Kreis.
Sie haben den Graph gegeben und Sie interessieren sich dafür, wie viel
Hamilton -Kreise es gibt.
Es kann ja durchaus Unterschiede, mehrere geben.
Das wäre ein Aufzählungsproblem.
So, jetzt haben wir für diese Art von Problemen das Gefühl, dass sie
mindestens so schwer sind, wie das entsprechende Entscheidungsproblem.
Das also zum Beispiel das Aufzählungsproblem für Hamilton-Kreis oder
das Suchproblem für Hamilton-Kreis mindestens so schwer ist, wie das
Entscheidungsproblem für Hamilton-Kreis.
Entscheidungsproblem kann man recht leicht beweisen, das ist NP
-vollständig.
Das heißt also, die anderen, das Suchproblem zu Hamilton-Kreis, das
Aufzählungsproblem zu Hamilton-Kreis ist dann mindestens so schwer wie
NP -vollständig.
Und den Problemen können Sie jetzt noch nicht mal sagen, die sind in
NP, weil die einfach von der Art, wie sie gestellt sind, da nicht
reinpassen.
Eins vorne weggenommen, das kommt in der nächsten Vorlesung, wenn man
so ein Problem hat, was noch nicht mal in NP ist, von dem man das
nicht beweisen kann, wo man es nicht weiß, von dem man aber zeigen
kann, es ist mindestens so schwer, wie die NP-vollständigen Probleme.
Dann sagt man bei so einem Problem, das ist NP-schwer.
Wenn Sie den Begriff NP-schwer sehen in der Literatur, dann trifft das
sozusagen diese Art von Problemen, die so schwer sind wie die NP
-vollständigen, aber von denen man noch nicht mal weiß, ob sie in NP
sind.
Für NP-vollständige kann man natürlich auch sagen, sind NP-schwer.
Das ist so das übliche Wort, dass man für Probleme, die erst gar nicht
als Entscheidungsproblem formuliert sind, wie zum Beispiel das
Optimierungsproblem von TSP, die aber mindestens so schwer sind, wo
das Entscheidungsproblem NP-vollständig ist.
Da sagt man zum Beispiel dann so, das ist ein NP-schweres Problem.
So und formal sozusagen die Reduktion von so einem Problem, das ein
Suchproblem ist, zu NP-vollständigen Problemen, dazu gibt es eben auch
eine Definition und dazu definieren wir erstmal eine Relation, die
jeder Instanz eines Suchproblems eine Lösung zuordnet.
Und dann sagen wir, eine Funktion realisiert diese Relation, wenn sie
einer Instanz, für die es eine Lösung gibt, eine zuordnet.
Und ansonsten Y,
ansonsten, also wenn die Instanz keine Lösung hat, der Y zuordnet.
Dann wird damit die Relation R realisiert, nämlich für jedes X haben
wir so ein Y, XY aus R, beziehungsweise wenn X keine Lösung Y
existiert, dann ist das XY.
Und wir sagen, ein Algorithmus löst das durch diese Relation
beschriebene Suchproblem, wenn er eben diese, so eine Funktion
berechnen kann, die Relation realisiert.
Und um jetzt sozusagen solche Suchprobleme zu reduzieren auf entweder
vollständige Probleme, benutzt man eine Oracle-Turing-Maschine, die
aber was anderes ist als eine nicht-deterministische.
Es ist jetzt ein bisschen blöd, dass sie Oracle-Turing-Maschine heißt,
aber so heißt sie nur mal in der Literatur und die ist folgendermaßen
definiert, das ist eine deterministische Turing-Maschine, die
äquivalent ist zu dem Modell der deterministischen Turing-Maschine,
das wir bisher betrachtet haben, aber die hat halt noch so ein Oracle
-Modul und das Oracle-Modul ist so eine Funktion, die also einem Wort
über dem Eingabealphabet, ein anderes Wort über dem Eingabealphabet
zuordnet.
Also eine Oracle-Turing-Maschine ist eine deterministische Turing
-Maschine, die hat zusätzlich ein ausgezeichnetes Oracle-Band und zu
den üblichen Zuständen, die man so kennt bei einer deterministischen
Turing -Maschine, hat sie noch zwei Zustände, QF und QA.
QF steht für Fragezustand, QA steht für Antwortzustand und QF und QA
gehören hier zu diesem Oracle-Band.
Die Arbeitsweise ist eben die, solange wir nicht in QF kommen,
arbeitet die Turing-Maschine ganz normal wie eine deterministische
Turing -Maschine und wenn wir nach QF kommen und wird nachgeguckt, wo
steht der Kopf, der zum Oracle-Band gehört.
Wenn der Kopf auf Position I des Oracle-Band steht und an der Stelle 1
bis I Wort Y steht, dann macht die Oracle-Turing-Maschine folgendes,
wenn das Y, also wirklich ein Wort über dem Eingabealphabet ist, dann
löscht es das Wort in einem Schritt und schreibt das Bild des Wortes
unter dieser Funktion G aufs Band.
Und dann ist der Folgezustand QA, der Antwortzustand, der sagt so, das
ist jetzt die Antwort auf die Frage.
Wie gesagt, die Oracle-Turing-Maschine ist was anderes als eine nicht
-deterministische Turing-Maschine, denn die macht immer dasselbe.
Die macht in so einer Situation, auf dem Oracle-Band steht Y und ich
bin in den Zustand QF gekommen, immer dasselbe, nämlich sie schreibt G
von Y über das Y drüber.
Insofern ist das was anderes als dieses in Anführungszeichen Oracle,
das wir uns bei der nicht-deterministischen Turing-Maschine als
Veranschaulichung vorgestellt haben.
Und dann kann man eine Turing-Reduktion definieren.
Wir haben zwei Relationen gegeben über eine Eingabealphabet Sigma und
eine Turing-Reduktion von der einen Relation auf die andere.
Einfach, sie stellen sich als Relation jetzt unter Relation so ein
Suchproblem vor.
Suchproblem, eine Relation ordnet eine Eingabe, eine Ausgabe vor, das
ist genau das Lösen eines Suchproblems.
So, und jetzt wird also eins auf das andere überführt durch eine
Oracle -Turing-Maschine M, deren Oracle gerade R' realisiert und die
selbst in polynomialer Zeit die Funktion berechnet, die R realisiert.
Dann haben sie, falls R' in polynomialer Zeit realisierbar ist und R
polynomial Turing transformierbar auf R', dass auch R' in polynomialer
Zeit realisierbar ist.
Sie haben jetzt sowas wie eine polynomiale Transformation zwischen NP
-vollständigen Problemen, zwischen solchen Suchproblemen.
Und da haben sie auch wieder Transitivität.
Und dann nennen wir eben ein Suchproblem Pi, NP schwer, falls es eine
NP -vollständige Sprache gibt, die sich Turing transformieren lässt
auf die Sprache zu Pi.
Also ich bin da jetzt ein bisschen schnell rübergegangen, obwohl das
vielleicht nicht so ganz leicht zu verdauen ist.
Was ich Ihnen damit zeigen will, ist einfach, dass man sozusagen
Probleme, die nicht als Entscheidungsprobleme formuliert sind,
sozusagen anschließen kann an unsere NP-vollständigen Probleme.
Da gibt es eben auch ein Mechanismus, um zu zeigen, so ein Problem ist
mindestens so schwer wie ein NP-vollständiges Problem, nämlich über
Turing -Reduzierbarkeit.
Und TSP-Suchproblem ist eben NP schwer, weil man das TSP-Suchproblem
in der Variante 1, wie wir es eh haben, eben hat sozusagen mit so
einer Turing-Reduktion auf das TSP-Entscheidungsproblem reduzieren.
Beweiskitze, also ich betrachte sozusagen das Entscheidungsproblem zu
TSP und ich betrachte das Suchproblem zu TSP und die zu den beiden
zugehörigen Relationen zum Entscheidungsproblem.
Die zugehörige Relation sieht einfach so aus, eine Instanz wird Ja
oder Nein zugeordnet.
Also, für die x Ja-Instanzen von TSP-Entscheidungsproblemen wird x J,
J für Ja zugeordnet.
Die Relation zum Suchproblem ist eine Instanz, das TSP-Problem wird
eine Lösung, eine Tour zugeordnet.
Die Relation zum Suchproblem ist so eine x x Instanz, das TSP-Problem
wird eine Y, Y Lösung zugeordnet.
So, und dann kann man das eine Turing reduzieren auf das andere oder
eine Turing-Transformation von der Relation zum Entscheidungsproblem
auf die Relation zum Suchproblem vornehmen.
Dafür müssen wir so eine Oracle-Turing- Oracle ist einfach so eine
Funktion, die ein Wort aus Sigma-Stern an Wort aus Sigma-Stern
abbildet und die realisiert eben die Relation zum Suchproblem und die
arbeitet jetzt folgendermaßen für eine Eingabe, schreibe die Eingabe
auf das Oracle-Band und gehe in den Fragezustand über, weise dann das
Oracle an, in einem Schritt das Bild des Oracles unter der Funktion Q,
unter der Funktion Omega hinzuschreiben und gehe dann in den Zustand
QA über und dann wird einfach überprüft, ob Omega von W eine Tour der
Länge kleiner gleich K kodiert.
Falls ja, lösche das Band und schreibe Ja, andernfalls lösche einfach
das Band und dann realisiert die gegebene Turing-Maschine Turing
-Maschine realisiert die Relation zum Entscheidungsproblem und hat
eine polynomial beschränkte Laufzeit.
Wie gesagt, diese letzte Viertelstunde war Exkurs in der Welt, also in
der Übung, nicht mehr weiter vertiefen werden, also es war jetzt nur
noch so ein bisschen Add-on, um zu sehen, das geht noch weiter und
auch eben Schwierigkeit von Problemen und insbesondere Probleme, die
nicht wie Entscheidungsprobleme aussehen, da irgendwie in den Kontext
zur NPV-Ständigkeit zu bringen, das hat eine saubere Grundlage.
Okay, das wäre es für heute.