So, herzlich willkommen.
Kurzer Soundcheck, neues Mikro, die Lautstärke stimmt soweit?
Okay.
Dann willkommen zur Vorlesung Theoretisch Grundlagen der Informatik.
Das allererste, was ich heute sage, ist, dass wir eine kleine Änderung
haben in unserem Ablaufplan.
Also wir haben es schon zur Hälfte durch, würde ich sagen.
Heute ist der 4.12., da ist die Vorlesung.
Und wir werden gleich am Donnerstag wieder eine Übung haben.
Und danach ab dieser Übung wieder in dem gewohnten Rhythmus Vorlesung,
Vorlesung, Übung, Vorlesung, Vorlesung, Übung, Vorlesung, Vorlesung,
Übung und so weiter.
Und am 10.01., da gibt es nichts, das wurde Ihnen, glaube ich, aber
auch schon angekündigt.
Gut.
So, das war zu den neuen Terminen.
Lassen Sie uns noch kurz einen Blick werfen auf das, was wir letzte
Vorlesung gemacht haben.
Ich hatte dieses Bild, so oder so ähnlich, da dran zu stehen.
Und das ist sozusagen ein Venn-Diagramm von verschiedenen Klassen von
Problemen oder Sprachen, Entscheidungsproblemen.
Da haben wir ganz groß die Klasse NP.
Und da drin enthalten ist die Klasse P. Das sind sozusagen die
polynomiell entscheidbaren Sprachen.
Und dann hatten wir welche, von denen wir nicht denken, dass sie
polynomiell entscheidbar sind, weil wir nicht glauben, dass P gleich
NP ist, was aber theoretisch noch möglich wäre.
Und dann hatten wir uns Kandidaten überlegt, die so schwer sind, dass
wenn so ein Kandidat, sowas wie Sat hier, in P wäre, dann wäre schon
die ganze Klasse NP in P enthalten.
Diese Sprachen hießen NP-vollständig.
Das waren Sprachen oder Entscheidungsprobleme, die sind so schwierig,
sie gehören zu den schwierigsten in NP.
Und dann hatten wir Reduktionen gemacht, um zu zeigen, dass wenn Sat
schwierig ist, was wir bewiesen haben, dann ist auch Drei-Sat
-schwierig.
Wenn Drei-Sat-schwierig ist, dann ist auch Klick schwierig und so
weiter.
Und so hatten wir diese fünf Probleme und ich glaube noch mehr
kennengelernt.
Was wir heute zunächst tun wollen ist, wir wollen da noch ein paar
Probleme dazu tun.
Und dann im zweiten Teil der Vorlesung werden wir was, wie ich finde,
angenehmeres machen.
Wir werden einen kleinen Blick über den Tellerrand werfen.
Nämlich, wir werden uns fragen, was ist eigentlich dazwischen?
Was ist da draußen?
Was ist nicht in NP?
Oder was ist eventuell zwischen P und NP?
Also gibt es was, was zwar noch nicht NP-vollständig ist, aber auch
nicht in P?
Ja, das wird dann im zweiten Teil der Vorlesung sein.
Aber zuerst lernen wir drei neue Probleme kennen und Reduktionen.
Ich verspreche, auch die Reduktionen sind nicht so schwierig wie
davor.
Und die Probleme sind insbesondere wichtig, weil wir zum Beispiel für
Knapsack uns dann noch konkrete Algorithmen angucken werden in
folgenden Vorlesungen.
Also, aber wir fangen an mit SubsetSum, was wir beweisen werden, dass
es NP-vollständig ist, durch eine Reduktion von ExactCover, was Sie in
der letzten Vorlesung kennengelernt haben, auf SubsetSum.
Zunächst die Problemdefinition.
In SubsetSum sehen die Instanzen wie folgt aus.
Wir haben eine endliche Menge, groß M, und eine Gewichtsfunktion, die
einfach eine Abbildung ist von M in die nicht negativen natürlichen
Zahlen.
Das heißt einfach nur jedes Element aus dieser Menge hat ein Gewicht.
Und außerdem haben wir eine Zahl K, und wir fragen uns, existiert eine
Teilmenge dieser Menge, sodass die Gewichte in dieser Teilmenge
aufsummiert genau K ergeben.
Okay, also Sie können sich so vorstellen, das sind wirklich, in M sind
wirklich Gegenstände, und jedes hat ein Gewicht.
Und wir fragen uns, kann ich von den Gegenständen, die da auf dem
Tisch liegen, kann ich mir irgendeine Teilmenge wählen, sodass sie
zusammen genau K wiegen.
Okay, das ist das Problem.
Gut, und wie schon angekündigt, wir werden diesen Satz beweisen, dass
SubsetSum nämlich np-vollständig ist.
Noch eine kleine notationelle Feinheit.
Es ist irgendwie heute in der Vorlesung ganz oft der Fall, dass wir
über so eine Summe reden, von irgendwie Gewichten über Elemente aus
einer Teilmenge, und wir benutzen dann so eine Kurznotation.
Wir sagen einfach, das Gewicht der Teilmenge ist die Summe der
Gewichte der Elemente der Teilmenge.
Okay, einfach damit wir nicht die ganze Zeit Summenzeichen schreiben
müssen.
Also das Gewicht einer Teilmenge ist die Summe der Gewichte der
Elemente in dieser Teilmenge.
Okay, und dann hier oben könnte ich das jetzt gleich schon
vereinfachen und sagen, die Frage bei SubsetSum ist, gibt es eine
Teilmenge m' von m, sodass das Gewicht dieser Teilmenge genau K ist.
Gut, also was müssen wir zeigen, damit wir np-Vollständigkeit zeigen?
Immer zwei Sachen.
Das Erste, einfache, dieses Entscheidungsproblem ist in np.
Das heißt, es gibt eine nicht-deterministische Turing-Maschine, die in
polynomialer Zeit das Problem löst.
Oder, so wie wir es uns anschauen mit Orakel-Turing-Maschine, es gibt
ein geeignetes Orakel, was in polynomialer Zeit verifiziert werden
kann.
Okay, und hier wäre das Orakel natürlich, das Orakel verrät uns diese
Teilmenge m', die wir ja suchen.
Und wenn uns das Orakel diese Teilmenge m' von m gibt, dann können wir
in polynomialer Zeit entscheiden, ob das tatsächlich eine Teilmenge
von m ist, ob das Gewicht dieser Teilmenge, also die Summe der ganzen
Elemente, die kann ausgerechnet werden und mit K verglichen werden.
Und dann wird geguckt, ist es genau K?
Dann ja.
Ist es nicht K, mehr oder weniger?
Dann nein.
Gut, also das Problem ist in np.
Für die Vollständigkeit machen wir eine Reduktion von einem
bekanntermaßen np.-schweren Problem.
Und wir wählen hier ExactCover.
Und für ExactCover müssen wir jetzt, also wir wollen sagen, wir
behaupten, wenn wir SubsetSum lösen könnten, dann könnten wir auch
ExactCover lösen.
Das heißt, wir müssen mit beliebigen Instanzen von ExactCover umgehen
können.
Wie sahen die nochmal aus?
So eine Instanz, so eine beliebige ExactCover Instanz sieht so aus,
dass wir eine Menge x haben, von irgendwelchen m Elementen, die obdA
einfach 0 bis m-1 heißen.
Und wir haben S, das ist eine Familie von Teilmengen von x.
Und die Frage war, gibt es eine Auswahl von ein paar von diesen
Teilmengen, sodass deren Vereinigung x ist und jedes Element genau
einmal genommen wurde dabei.
Okay, das war die Fragestelle bei ExactCover.
Wir geben so eine beliebige Instanz, konstruieren wir uns jetzt eine
SubsetSum Instanz und müssen dann zeigen, dass diese SubsetSum Instanz
genau dann lösbar ist, wenn die ExactCover lösbar war.
Okay.
So, wie machen wir das?
Also wir sagen, bei ExactCover, da werden ja jetzt hier irgendwie
Elemente aus diesen Teilmengen gewählt.
Da wird eine Auswahl von Teilmengen getroffen.
Das heißt, in SubsetSum, da werden Auswahl von Gegenständen getroffen.
Also sollten unsere Gegenstände m unsere Teilmengen s sein.
Okay.
Und das Gewicht eines Gegenstandes müssen wir auch noch definieren und
wir werden das als eine Zahl p hoch x, also die Gegenstände x sind ja
Zahlen, die sind einfach durchnummeriert.
Das soll sozusagen p hoch der Index dieser Zahl sein für ein ganz
bestimmtes p.
Okay.
Und zwar, wie wird dieses p errechnet?
Das p ist die, also wir gucken uns zuerst an für einen Element x, die
Häufigkeit von x in dieser Menge, in dieser Familienmenge von Mengen
s.
Also das ist die Anzahl der y in s, die x enthalten.
Okay.
Also wie oft ist x in einem Element von y, in einem Element y von s
enthalten.
Und p soll einfach größer sein als alle diese Häufigkeiten.
Ich habe jetzt hier die größte Häufigkeit plus 1 gewählt, aber
Hauptsache größer als alle Häufigkeiten.
Das wird dann wichtig später.
Okay.
Und dann ist das Gewicht eines einzelnen Elementes ist p hoch x und
dann ist das Gewicht einer Menge die Summe der Gewichte der Elemente
und so weiter.
So, jetzt haben wir für unsere subset-sum-Instanz, jetzt haben wir die
Gegenstände gefunden und wir haben das Gewicht eines Gegenstands
gefunden.
Und wir müssen jetzt noch dieses Groß-K bestimmen, was dieses
Zielgewicht ist, wo wir bei subset-sum nachfragen.
Und das definieren wir uns.
K ist einfach das Gewicht der ganzen Menge m, also alle p hoch x
einmal aufsummiert.
Also p hoch 0 plus p hoch 1 plus p hoch 2 und so weiter.
Gut.
Am besten machen wir das einem... Achso, ganz kurz noch, das ist
natürlich wichtig in unserer Konstruktion, Polynomialzeit.
Das heißt, wir haben eine Instanz gemacht, die ist nicht zu groß.
Die ist nur polynomiell groß in der Exact-Cover-Instanz.
So, auf der rechten Seite sehen wir vielleicht mal ein Beispiel.
Dann wird es ein bisschen klarer.
x ist die Menge, die aus der Exact-Cover kommt.
Wir fragten uns, ob diese Menge 0 bis 6 genau überdeckt werden kann
durch eine Auswahl von Teilmengen von dieser Menge.
Und jetzt zum Beispiel ist y 0 2 5 ist jetzt zum Beispiel so eine
Teilmenge, die zur Verfügung steht, um ausgewählt zu werden für Exact
-Cover.
Dann bestimmen wir dieses p, wie auch immer das aussieht und dann ist
das Gewicht dieser Teilmenge jetzt für die Subset-Sum-Instanz ist p
hoch 0 plus p hoch 2 plus p hoch 5, weil es einfach das 0., das 2.
und das 5.
Element war.
Okay.
Also wir können das auch schreiben, wenn wir das jetzt in Darstellung
mit zur Basis p schreiben, dann ist das einfach... habe ich die falsch
rum umgedreht.
Eigentlich müsste der p hoch 0-Term ganz hinten stehen, aber ist egal.
Ich habe die jetzt... ist das eine komische Darstellung zur Basis p,
wo alles vorne rückwärts gelesen wird.
Okay, dann haben wir einfach 1 mal p hoch 0 plus 0 mal p hoch 1 plus 1
mal p hoch 2 plus 0 mal p hoch 3 plus 0 mal p hoch 4 plus 1 mal p hoch
5 plus 0 mal p hoch 6.
Okay, das ist einfach die Darstellung in p-artischer Schreibweise.
Leider falsch rum.
Okay.
Also jetzt sieht man schon, warum man an dem Gewicht sozusagen die
Teilmenge wieder ablesen kann.
Das Gewicht ist ja nur eine Zahl und da sehen wir, dass wir die
Teilmenge wieder ablesen können, indem wir einfach sagen, dass das hat
eine 1 an der Stelle, wenn das Element in der Teilmenge ist und eine 0
sonst in dieser Darstellung.
Und das Zielgewicht ist das, wo überall Einsen stehen.
Das war ja gerade die Summe über alle p hoch x.
Und jetzt ist es so, dass wenn wir zwei Teilmengen wählen für die
Exact Cover, dann wählen wir sozusagen diese beiden Elemente in der
Subset Sam und betrachten uns die Summe der Gewichte.
Das heißt, wir werden diese Zahlen hier addieren.
Und dann addieren wir die... naja, wenn die des Jungs sind, die
Teilmengen, dann haben die nicht auf der gleichen Stelle eine 1.
Und wenn dann zwei Nullen aufeinandertreffen in dieser p-artischen
Darstellung, bleibt es eine 0.
Eine 1 auf eine 0 trifft zusammen, wird eine 1 und so weiter.
Wenn zwei Einsen aufeinandertreffen, dann wird es was anderes.
Dann wird es eine 2.
Und das Wichtige war, dass das p groß genug ist, dass wenn die beiden
Einsen aufeinandertreffen, dass es wirklich eine 2 wird und nicht
irgendwie so ein Übertrag gibt und es wieder eine 0 wird und es in der
Stelle weiter wird eine 1.
Deswegen war das p groß genug gewählt, dass es einfach nicht möglich
ist, die Teilmenge... selbst wenn ich alle zusammenwähle, wird nicht
genügend Gewicht da sein, um diesen Übertrag zu kriegen in dieser p
-artischen Addition.
Gut, das ist die Idee dahinter.
Hier unten steht es nochmal.
Also wir stellen die Mengenzugehörigkeiten als Zahlen zur Basis p dar.
Wir kodieren dann diese Zahl w von y in p-artischer Darstellung, also
einfach als String aus Nullen und Einsen, wobei an der i-ten Stelle
eine 1 steht, wenn i aus der Menge kommt.
Die erste Stelle ist jetzt hier die 0-te Stelle sozusagen.
Und entsprechend ist k der String, der einfach nur m Einsen hat.
Gut, so das ist die Anschauung und jetzt müssen wir noch beweisen,
dass das das Gewünschte tut.
Das müssen wir mal zeigen.
Achso, vorher kommt noch was.
Das, was ich gerade schon gesagt habe.
Wenn wir jetzt die Strings addieren, weil wir die entsprechenden
Teilmengen alle wählen, dann addieren wir diese Zahlen in der p
-artischen Darstellung und dann heißt es, dass wir immer einen String
der Länge m haben und an der i-ten Stelle haben wir, wie viele von den
gewählten y und j haben jetzt dieses id-Element.
Und das Ziel ist ja, die y und j so zu wählen, dass jedes Element
exakt einmal gewählt wird, also dass dieser String 1 1 1 1 1 1
rauskommt.
Hier noch mal ein Beispiel, wo wir auch das mit dem p sehen.
Also wenn das ist eine ganz konkrete Instanz von ExactCover.
Wir haben 1 2 3 4 mögliche Teilmengen 0 0 2 5 0 1 2 2 4 5 und 3 4 6.
Die könnten wir wählen, das heißt wir werden in unserer subset-sum
-Instanz 4 Gegenstände haben.
Jetzt müssen wir erstmal das p bestimmen, das heißt wir gucken uns so
jeder von diesen Zahlen 0 bis 6 an, wie oft sie vorkommt.
Die 0 kommt zweimal vor, die 1 kommt nur einmal vor, die 2 kommt
dreimal vor, die 3 kommt einmal vor, die 4 zweimal, die 5 einmal und
die 6 einmal.
Das heißt 3 war die häufigste Häufigkeit, das heißt wir wählen das p
als 4.
Ja, das ist schon richtig.
Ja, was richtig ist, dass das k die w von x sein muss und nicht von m.
Das ist richtig, aber hier oben stimmt es.
Also unsere Gegenstände sind die Teilmengen, die wir wählen können.
Weil wir in der ExactCover Instanz haben wir diese Teilmengen zur
Auswahl und können es immer entscheiden nehmen oder nicht nehmen.
Deswegen sollten das unsere Gegenstände sein für die subset-sum.
Was richtig ist, was sie richtig sagen ist, dass das k soll das
Gesamtgewicht aller Elemente und nicht das Gesamtgewicht aller
Teilmengen sein.
Und deswegen müsste hier, also das rechte ist richtig, die Summe
stimmt, aber hier müsste w von x stehen und nicht w von m.
Okay, so und jetzt haben wir hier nochmal diese vier Mengen einfach
kodiert in dieser vierartigen Darstellung.
Und das sind diese Strings und die Frage ist, kann ich die so
addieren, dass 1, 1, 1, 1, 1, 1, 1, 1 rauskommt.
Gut.
So, jetzt müssen wir zeigen, dass das das richtige tut, nämlich ja
Instanz von dem Original ExactCover Problem genau dann, wenn ja
Instanz von dem kreierten subset-sum Problem.
Zwei Richtungen zu zeigen.
Zuerst nehmen wir an, es war eine ja Instanz von dem ExactCover
Problem und wir müssen zeigen, es ist eine ja Instanz von dem subset
-sum Problem.
Also wir wissen, dass es jetzt eine ja Instanz, das heißt es existiert
eine Lösung und eine Lösung sieht so aus, dass es es Strich gibt, eine
Auswahl von diesen Teilmengen aus S, die eine exakte Überdeckung
bilden.
Also die Vereinigung von diesen Mengen ist genau ganz X und jedes
Element wurde einmal gewählt.
Und jetzt gucken uns diese Auswahl an Teilmengen an, interpretiert als
eine Auswahl von Elementen in der subset-sum Instanz und gucken, was
uns jetzt interessiert, ist das Gewicht dieser.
Also wir summieren W von Y über die Y aus S Strich.
Das ist jetzt aber einfach... W von Y ist ja das Gewicht jedes
einzelnen Elements in Y, also die Summe über P von X, über alle diese.
Und wir wissen jetzt, dass jedes X taucht genau einmal auf in dieser
Doppelsumme.
Also jeder P von X-Term wird genau einmal auftauchen.
Genau einmal kommt irgendwo P von 0, genau einmal kommt irgendwo P
hoch 1 und so weiter.
Das heißt, das ist das gleiche wie die Summe X gleich 0 bis M minus 1
P hoch X.
Und das ist ja genau das K, so wie wir es definiert haben.
Das heißt, diese Gleichung sagt uns, dass diese Auswahl eine Lösung
für subset-sum ist.
Also subset-sum diese Instanz ist lösbar.
Die eine Richtung.
Die andere Richtung analog.
Wir wissen jetzt, die subset-sum Instanz ist lösbar.
Das heißt, wir kriegen eine Auswahl von den Gegenständen.
Wir interpretieren das als eine Auswahl von Teilmengen.
Und jetzt muss irgendwann ja noch der Punkt kommen, dass das P richtig
gewählt wurde, damit das alles funktioniert.
Also wir haben jetzt die Auswahl an Teilmengen und wir nennen die
jetzt gleich als S-Strich.
Das ist die subset-sum-Lösung.
Wir wissen, dass die Summe über diese Gewichte genau K ist.
Und K ist ja, wie definiert, ist die Summe über diese P hoch X.
Jetzt ist die Frage, heißt das, dass wir jeden P hoch X Term genau
einmal aufgesammelt haben.
Und das ist jetzt nach der Definition von P muss das so sein, dass
jedes X genau einmal aufgesammelt wurde, weil wenn wir so ein X
zweimal aufgesammelt haben oder mehrmals, wir haben es höchstens P-1
mal aufgesammelt, weil das die höchste Häufigkeit eines Elements ist.
Und P hoch P, genau, P hoch P-1,
was bin ich jetzt?
Nein, P-1 mal, genau, wir addieren die Terme.
Wenn wir P-1 mal P hoch X gemacht haben, dann ist das noch nicht P
hoch X plus 1.
Weil es ja nur P-1 mal P hoch X ist.
Und es ist einfach weniger als P hoch X plus 1.
Das heißt, in dieser Dezimaldarstellung würden wir dann eine echt
größere Zahl als 1 sehen.
Gut, das ist die Wahl von P, die uns sagt, dass das alles genauso ist,
wie wir uns das denken.
Und das Strich ist dann wirklich eine exakte Überdeckung von der Exact
Cover Instance.
So, das war das erste Problem.
Subset Sum.
Das nächste ist Partition.
Partition sieht erst mal ganz ähnlich aus und deswegen ist die
Reduktion auch relativ leicht.
Wir haben bei Partition wieder eine endliche Menge von Gegenständen
und jeder Gegenstand hat ein Gewicht, so wie vorher auch.
Jetzt haben wir aber keine Zahl K, kein Zielgewicht mehr, sondern das
Ziel ist es, die Gegenstände in zwei Mengen aufzuteilen.
Irgendwie ein paar nach links zu schieben und ein paar nach rechts zu
schieben, so dass das Gewicht auf der linken Seite exakt gleich ist,
wie das Gewicht auf der rechten Seite.
Wir wollen sozusagen die Gegenstände auf so eine Balance-Waage
stellen, dass das genau im Gleichgewicht ist.
Und die Frage ist, existiert eine Teilmenge M Strich, das ist
sozusagen die, die links auf die Waage kommt, so dass das Gewicht, das
Gesamtgewicht dieser Teilmenge, das gleiche ist, wie das Gewicht der
übrig gebliebenen.
Das ist dann das, was rechts auf die Waage kommt.
Kleiner, aber feiner Unterschied.
So, das Problem Partition ist auch NP-Vollständig, wie wir jetzt
zeigen werden.
NP-Vollständigkeit wird gezeigt in zwei Schritten.
Der erste Schritt, das Problem liegt in NP.
Wenn uns das Orake verrät, was links auf die Waage kommen soll, dann
können wir in Polynomialzeit ausrechnen, was ist das Gesamtgewicht
dieser Menge und was ist das Gesamtgewicht der übrig gebliebenen
Elemente und können die beiden vergleichen und wirklich sagen, ja, die
sind gleich.
Oder nehm ich.
Also das Problem liegt in NP.
Jetzt die Reduktion.
Subset-Sum ist schon schwer und wir wollen zeigen, dass Partition
schwer ist.
Das heißt, wir wollen sagen, wenn wir Partition lösen können, wenn wir
das einfach lösen können, auf die Waage verteilen, dann können wir
auch einfach Teilmengen mit Gewicht genau k rausfinden.
Also wir gehen davon aus, wir haben eine beliebige Instanz von Subset
-Sum, wo die Aufgabe ist, eine Teilmenge mit Gewicht k rauszufinden
und wir kreieren uns jetzt neue Gegenstände, sodass diese Gegenstände
können genau in zwei gleich große, gleich schwere Mengen aufgeteilt
werden, wenn vorher es so eine Teilmenge mit Gewicht k gab.
Gut.
Bei den Gegenständen, wir machen nicht allzu viel, wir lassen alles,
was wir gegeben haben für die Subset-Sum Instanz gleich, auch die
Gewichte, nur dass wir noch zwei neue Gegenstände hinzufügen.
Die heißen jetzt hier klein b und klein c.
Die sind einfach zwei neue Gegenstände und wir geben diesen
Gegenständen ein ganz spezielles Gewicht.
Und zwar b kriegt das Gewicht n-k.
k wissen wir, das ist die Frage aus der Subset-Sum.
Und was ist N?
N ist das, was alles zusammen wiegt, plus 1.
Okay.
Also wenn k relativ klein ist, dann ist b ziemlich klein.
Und b ist ziemlich schwer.
Das Gesamtgewicht aller Sachen, die wir dort haben, nur ein bisschen
das k abgezogen.
Oder wenn k ziemlich groß ist, ist das hier ziemlich klein.
Und dafür ist dann das andere, das Gegenstück, klein c.
Und klein c ist k plus 1.
Okay.
Also machen wir wieder ein Beispiel.
Also wenn vorher bei Subset-Sum wir vier Gegenstände hatten, die
einfach jetzt i, j, k und l heißen und zum Beispiel von j das Gewicht
13 war, dann haben wir in unserer Partition-Instanz immer noch die
gleichen vier Gegenstände und zwei weitere, b und c.
Und das Gewicht von j ist immer noch 13.
Ich habe jetzt bloß w-Sternen dran geschrieben, um zu sagen, das ist
jetzt die Gewichtsfunktion aus der Partition-Instanz.
So.
Wir beobachten, dass diese Reduktion in polynomialer Zeit geht.
Das heißt, was noch bleibt, ist zu zeigen, ja-Instanz aus Subset-Sum,
genau dann, wenn ja-Instanz aus Partition.
Also was heißt das ja-Instanz aus Partition?
Ja.
Ja-Instanz aus Partition hier auf der linken Seite.
Nochmal, das ist die Bedingung.
Es gibt m-Strich aus m-Stern mit dem Gewicht w-Stern von m-Strich,
genau das wie w-Stern von dem übrig gebliebenen.
Und ja-Instanz aus der Subset-Sum heißt, es gibt eine Teilmenge, die
nennen wir jetzt m-2-Strich aus m, deren Gewicht genau k ist.
Gut.
Jetzt machen wir noch zwei kleine Beobachtungen.
Und zwar, wie haben wir diese Gewichte von dem b und dem c gewählt?
Wenn wir die zusammenaddieren, dann ist es n-k und k-plus-eins ist n
-plus -eins.
Okay.
Also b und c zusammen sind so schwer wie-n war ja w von m-plus-eins.
Das heißt, die sind schwerer als alles zusammen.
Als der Rest zusammen, sogar plus zwei.
Okay.
Insgesamt haben wir ein Gewicht von, naja, n-1 für das w von m.
Und b und c, also insgesamt haben wir ein Gewicht von genau 2n.
Also b und c, das ist wieder das Gleiche.
b und c sind zusammen genau zwei schwerer als der Rest, also ist ein
bisschen mehr als die Hälfte des Gesamtgewichts in der neuen Instanz
liegt auf b und c.
Das heißt, wenn wir jetzt in dieser, wo wir ja in der Partition
Instanz sind und versuchen wollen, die Waage auszugleichen, wir können
nicht b und c auf die gleiche Seite der Waage tun.
Die sind einfach schon schwerer als alles andere zusammen.
Da wird die Waage ausschlagen.
Okay.
Das heißt, die einzige Möglichkeit ist, naja, b auf die eine Seite und
c auf die andere Seite zu machen und dann die restlichen Gewichte so
zu verteilen, dass es dann ins Gleichgewicht kommt.
Ja.
Gut.
Und wir sagen jetzt einfach OBDA, dass b ist in dieser m' Menge, also
b ist auf der linken Seite der Waage und c ist in dem Rest, also auf
der rechten Seite der Waage.
Okay.
Gut.
So, und jetzt können wir loslegen.
Wir gehen jetzt erstmal von links nach rechts.
Wir nehmen an, die Waage kann ausgeglichen werden mit diesem b und c
und müssen zeigen, dass es dann eine Timing gibt, dessen Gewicht genau
k ist.
Also die Waage kann ausgeglichen werden, also sei m' so eine linke
Seite der Waage mit b da drin enthalten.
Dann, wir wissen ja schon, dass alle zusammen 2n wiegen, das heißt m'
muss ein Gewicht von genau n haben.
b hat ein Gewicht von n-k, das heißt, wenn ich da b raus entferne,
dann hat die Teilmenge m' n-n-k, also genau k.
Also das, was ich zu b dazu getan habe, damit die Waage ausgeglichen
ist, wenn b und c auf links und rechts verteilt sind, muss genau k
groß sein.
Das heißt, das wäre diese, was wir dazu getan haben, das wäre jetzt
eine Lösung von der SubsetSumInstanz.
Andersherum, wenn wir eine Lösung aus der SubsetSumInstanz haben, m'',
was wir dann tun ist, naja, wir tun das und b auf die linke Seite und
den Rest auf die rechte Seite.
Und wieder, was liegt jetzt hier auf der linken Seite?
Auf der linken Seite liegt diese Menge von hier oben plus das Gewicht
von b, also das ist k, und das Gewicht von b ist n-k, ist also genau
n, was genau die Hälfte des Gesamtgewichts ist.
Also die Waage ist ausgeglichen.
So, das zeigt, dass Partition auch np-vollständig ist.
Das letzte ist jetzt nebsec, wieder ganz ähnlich.
Wir haben eine Menge von Gegenständen und jetzt kommen die aber mit
zweierlei Wertungen.
Das eine ist Gewicht und das andere ist Kosten.
Also man stellt sich immer vor, dass das ein Räuber steigt irgendwo
ein und er sieht jetzt da, wo er eingestiegen ist, eine ganze Menge
von Gegenständen und die haben alle ein Gewicht, was schlecht für ihn
ist, weil er die tragen muss, und die haben alle ein Kostenpunkt, was
gut für ihn ist, weil er die zu Geld machen kann.
Und jetzt gibt es zwei Zahlen, w und c, und die Frage ist, kann der
Räuber eine Teilmenge von den Sachen, die ihm da zur Verfügung stehen,
sozusagen auswählen, die zusammen höchstens w wiegen, das ist
sozusagen, was er maximal tragen kann, ihm aber zusammen mindestens
groß c bringen als Ertrag.
Also der Räuber stellt sich die Frage, für meine Tragekapazität von
zehn Kilo und mein Gewinnvorstellung von 1000 Euro, ist es möglich aus
dieser Gegenstandsmenge, die ich dort sehe, welche auszuwählen, die
zusammen nur zehn Kilo wiegen, aber mir mindestens 1000 Euro bringen.
Das ist die knepseck Problemstellung.
Und wieder die Aussage ist knepseck ist NP vollständig.
Ich zeige Ihnen die Reduktion, die kommt, also erstmal wieder knepseck
muss in NP sein, also wenn uns das Orakel verrät, was wir mitzunehmen
haben, dann können wir ausrechnen, wie viel wiegt es insgesamt.
Wir können es vergleichen, ob das wirklich unsere Beschränkung groß w
einhält.
Wir können auch ausrechnen, wie viel bringt uns das zusammen, was sind
die Kosten von diesen Gegenständen und können das vergleichen, ob das
mindestens unserem groß c ist.
Also es liegt in NP, weil das alles in polynomial Zeit geht.
Die Reduktion ist jetzt von Partition.
Partition war das Problem, wo die Waage ausgeglichen werden sollte.
Ich zeige Ihnen die Reduktion, aber wir machen den Beweis mit diesem
hin und her nicht.
Also wir geben Partition, dieses Problem mit den Gegenständen, die
haben jetzt nur Gewichte und die Frage ist, können die auf die Waage
links und rechts verteilt werden.
Und die Idee ist jetzt natürlich, dass dieses links und rechts
verteilen soll so sein, mitnehmen oder nicht mitnehmen.
Wir müssen jetzt eine knepseck Instanz machen, das heißt wir haben,
was wir tun ist, wir nehmen die gleichen Gegenstände, m ist die
gleiche Menge.
Wir machen aber die Gewichtsfunktion ändern wir und zwar machen wir
alles doppelt so schwer.
Und die Kostenfunktion ist das gleiche wie die Gewichtsfunktion, c ist
auch zweimal w.
Und dann sagen wir unsere Trage, also jetzt sind die Gegenstände, die
haben sozusagen einheitliche Kosteneffizienz in ihrem Gewicht.
Also etwas, was fünf Kilo wiegt, bringt auch fünf Euro.
Okay, so haben wir das jetzt uns hin definiert.
Und jetzt ist die Sache, wir wollen höchstens 100 Kilo mitnehmen, aber
mindestens 100 Euro machen.
Naja und dann ist die einzige Möglichkeit, dass wir exakt 100 Euro
machen oder exakt 100 Kilo mitnehmen, weil nach unserer Definition
Gewicht und Kosten jetzt exakt das gleiche sind.
Okay, also in mathematischen Termen, groß W, das ist unsere
Tragekapazität und groß C, unsere Gewinnvorstellung, soll genau sein,
die Summe der ursprünglichen Gewichte, also das ist die Hälfte von
dem, was dort ist, weil wir ja hier alles verdoppelt hatten.
Die Frage ist, können wir jetzt exakt die Hälfte mitnehmen und das ist
obviously Partition.
Also wir müssen auch sagen, die Konstruktion geht in Polynomialzeit
und die Partitioninstanz mit der Waage ist eine Ja-Instanz, genau
dann, wenn die Knapsack-Instanz mit diesen speziellen Knapsack
-Gewichten eine Ja-Instanz ist.
Gut, und den Beweis machen wir hier aber nicht, aber die Idee sollte
klar sein und Sie sollten fähig sein, das auszuarbeiten.
Gut, so, das war's für NP-Vollständigkeitsreduktion, versprochen.
Jetzt haben wir das hier alles uns hergeleitet.
Ja, wir haben gezeigt, dass diese ganzen Probleme NP-Vollständig sind.
Wir haben gar nicht so viel über die Klasse P gesprochen, das soll
auch gar nicht Teil dieser Vorlesung sein, aber irgendwie, wir wollen
mal noch mal rekapitulieren, was jetzt eigentlich das Wichtige daran
war.
Also, das Wichtige ist diese Frage P gleich NP oder nicht.
Wir haben gesehen, dass es für je zwei NP-Vollständige Probleme eine
polynomiale Transformation von einem in das andere gibt.
Wir haben immer nur eine Richtung gezeigt, aber NP-Vollständigkeit an
sich heißt ja, dass alles auf dieses Problem reduziert werden kann.
Also die Rückrichtung kommt aus der Definition der NP-Vollständigkeit.
Das heißt, wenn wir zwei Probleme haben, zum Beispiel 3SAT und NEPSAC,
die sind beide NP-Vollständig, dann gibt es zwischen den beiden
polynomiale Transformationen in beide Richtungen.
Das eine ist, wenn ich 3SAT lösen möchte, dann kann ich diese 3SAT
Instanz umformen, sodass ich nur noch eine NEPSAC Instanz lösen muss.
Und diese Umformung ist zum Beispiel, wir folgen diesem Pfad.
Ich habe Ihnen gezeigt, wie man aus 3SAT COLOR macht, wie man aus
3COLOR EXECCOVER macht, aus EXECCOVER SUBSETSAM, aus SUBSETSAM
PARTITION und aus PARTITION NEPSAC.
Jetzt können wir das alles hintereinander schalten und dann kriegen
wir letztendlich aus der 3SAT Instanz eine NEPSAC Instanz.
Und die hätte die Eigenschaft, dass diese NEPSAC Instanz lösbar ist,
genau dann, wenn die 3SAT Instanz lösbar war.
Und andersherum geht natürlich auch, wenn ich NEPSAC habe, kann ich
das umformen in 3SAT, weil alles kann umgeformt werden in SAT, das ist
der Sat von COOK.
Da nimmt man also die Konstruktion aus dem Satz von COOK, wie man
NEPSAC in SAT umformt und SAT kann dann in 3SAT umgeformt werden, mit
der Reduktion.
Also wenn ich NEPSAC lösen will, dann kann ich das auch so
modifizieren, polynomial, sodass ich nur noch 3SAT lösen muss.
Das haben wir also gesehen.
Zu je zwei entweder vollständigen Problemen gibt es diese
Transformation ineinander.
Deswegen sagen wir, weil diese Zwischenschritte dazwischen sind
polynomial nur, auch wenn da mehrere von hintereinander ausgeführt
werden, das bleibt ja polynomial und das ist für uns vernachlässigbar.
Das heißt, wir sagen, diese Probleme sind im Wesentlichen gleich
schwer, brauchen die gleiche Laufzeit.
Ja, bis auf polynomiale Faktoren.
Das heißt jetzt, dass es Auswirkungen hat auf die Frage, ob P gleich
NP ist.
Wir beweisen den folgenden Satz.
Wenn L eine NP-vollständige Sprache ist, zum Beispiel ein NEPSAC, und
es stellt sich jetzt später heraus, dass L in P ist.
Irgendjemand kommt daher und findet eine deterministische
Turingmaschine, die NEPSAC in polynomialzeit löst.
Einfach ein Algorithmus, der deterministisch in polynomialzeit NEPSAC
löst.
Dann ist die Frage beantwortet, nämlich dann ist P gleich NP.
Dann kann alles, was in NP ist, effizient in polynomialzeit gelöst
werden.
Andersherum, wenn jemand später kommt und beweist, dass dieses Problem
L, was ja NP-vollständig ist, zum Beispiel NEPSAC, nicht in P ist,
also es wird bewiesen, dass es unmöglich ist, einen polynomialzeit
-Algorithmus aufzustellen, dann folgt auch, dass jede NP-vollständige
Sprache nicht in P ist.
Insbesondere ist dann P ungleich NP.
Das heißt, ich kann Ihnen leider nicht sagen, ob es für NEPSAC oder
DREISAT oder COLOR oder so einen polynomialzeit-Algorithmus gibt.
Wir wissen es nicht.
Wir vermuten nein, aber wir können es nicht beweisen.
Gut.
Gehen wir das einmal kurz durch, diesen Satz, den wollen wir noch
beweisen.
Der erste Teil.
Was haben wir?
Wir haben eine Sprache L, die ist NP-vollständig, aber gleichzeitig
polynomiell lösbar.
Dann wollen wir zeigen, dass P gleich NP ist.
Also, polynomiell lösbar heißt für uns, es gibt eine polynomiale
deterministische Turing-Maschine für L.
Jetzt wollen wir zeigen, dass P gleich NP ist.
Das heißt, jedes Problem in NP hat eine zugehörige Turing-Maschine,
deterministisch, polynomialzeit.
Schauen wir uns ein Problem L' aus NP an und wir wollen diese Turing
-Maschine aufstellen.
Naja, wir gucken uns die polynomiale Transformation an, von L' nach L'
und machen jetzt die Transformation, was als Turing-Maschine gedeutet
werden kann.
Die ist ja in polynomialzeit.
Jetzt haben wir das transformiert in eine L-Instanz.
Die können wir mit M lösen und lösen somit das Problem L'.
Und weil diese polynomiale Transformation plus die polynomiale Turing
-Maschine hier hinten zusammen immer noch polynomial ist, heißt es,
dass auch das Problem L' in polynomialzeit gelöst werden kann.
Der zweite Teil ist quasi die gleiche Aussage, aber gehen wir es
trotzdem noch mal durch.
Wenn jetzt jemand bewiesen hat, dass L nicht in P ist, obwohl es NP
vollständig ist, also es ist unmöglich so eine Turing-Maschine zu
bauen, dann wollen wir zeigen, dass jede NP-vollständige Sprache L'
auch nicht in polynomialzeit lösbar ist.
Wie für einen Widerspruchsbeweis, wenn jetzt eine andere NP
-vollständige Sprache L' doch in P sein sollte, naja, dann gilt für
L', der erste Teil, die ist ja NP-vollständig und die ist in P, dann
ist P gleich NP, also ist auch L', was ja in NP ist, in P Widerspruch.
Da beißt sich jetzt die Katze selbst ins Schwanz, es liegt daran, dass
die beiden Aussagen einfach Kontraposition voneinander sind und
eigentlich das gleiche Argument benötigen.
Gut.
Fassen wir noch mal ganz kurz zusammen, bevor wir diesen Blick über
den Tellerrand werfen.
Was haben wir in dieser Komplexitätstheorie kennengelernt?
Wir haben die Klasse P definiert, das sind Entscheidungsprobleme oder
Sprachen, die mit einer deterministischen Turing-Maschine in
polynomialer Zeit gelöst werden können.
Insbesondere sind diese Sprachen entscheidbar.
NP, Entscheidungsprobleme, die mit einer nicht-deterministischen
Turing -Maschine, wir haben uns das Orakel-Modell angeguckt, in
polynomialer Zeit gelöst werden können.
Die Anschauung hinter dem Orakel-Modell ist, wenn die Antwort bei
einer Eingabe Ja ist, also wenn das Wort aus der Sprache kommt oder
die Instanz eine Lösung hat, eine Ja-Instanz ist, dann gibt es einen
geeigneten Hinweis, ein Zeugen, sagen wir manchmal auch, der dann in
polynomialer Zeit verifiziert werden kann.
Wir können Ja-Instanzen, wenn sie uns gezeigt werden, erkennen.
Wenn uns gezeigt wird, das ist eine Ja-Instanz und deshalb ist sie
eine Ja-Instanz mit Hinweis, dann können wir das in polynomialer Zeit
erkennen.
Das ist die Klasse NP.
Wir haben dann polynomiale Transformationen eingeführt.
Für Sprachen sind diese Abbildungen aus dem Alphabet der ersten
Sprache in das Alphabet der zweiten Sprache wichtig, dass es
polynomial berechenbar ist.
Das heißt, es ist eigentlich eine deterministische Turing-Maschine,
die dahinter steht, die diese Transformation macht.
Polynomial-Zeit reicht für uns meistens, das Bild ist polynomial groß
von dieser Konstruktion.
Und Ja-Instanzen werden auf Ja-Instanzen abgebildet, also die
Lösbarkeit bleibt erhalten.
Und eine Sprache hieß dann NP-Vollständig, wenn sie in NP ist erstmal
und jede Sprache aus NP reduziert werden kann auf diese Sprache.
Also ich muss nur noch L lösen und dann kann ich alles aus NP lösen.
Alles kann ich überführen in eine L-Instanz.
Dann heißt L NP-Vollständig.
Und diese zwei Teile, die haben wir immer zusammen betrachtet und
immer gesagt NP-Vollständig.
Es ist denkbar, dass eine Sprache zum Beispiel nur die erste Bedingung
erfüllt.
Zum Beispiel alle Sprachen in P erfüllen die erste Bedingung, aber
wahrscheinlich nicht die zweite.
Es ist auch denkbar, dass Sprachen nur die zweite Bedingung erfüllen.
Die Sprache ist mächtig genug, wenn ich die lösen kann, kann ich alles
in NP lösen, aber die Sprache ist vielleicht sogar außerhalb von NP.
Deswegen sagen wir, wenn nur die zweite Bedingung gilt, auch die
Sprache ist NP-Schwer.
Im Gegensatz zu NP-Vollständig.
NP-Vollständig ist das gleiche wie NP-Schwer und in NP.
Und NP-Schwer heißt einfach nur schwer.
Einfach nur die Reduzierbarkeit.
So, die Bedeutung von dieser NP-Vollständigkeit oder NP-Schwere ist
unter der Annahme, dass P nicht gleich NP ist, was wir glauben, gibt
es kein polynomielles Lösungsverfahren für ein NP-Vollständiges
Problem.
Das heißt, das sind die Probleme, wenn wir zeigen, die sind NP
-Vollständig.
Wir müssen die Idee aufgeben, dieses Problem schnell und exakt lösen
zu können.
Wahrscheinlich.
Okay, deswegen machen wir das alles.
Gut.
Ja,
interessante philosophische Frage.
Ja, ein bisschen würde die Welt aus den Fugen geraten.
Also es kommt darauf an, wie gezeigt wird, dass P gleich NP ist.
Es gibt also verschiedene Szenarien, was passieren könnte.
Wenn jetzt jemand herkommt und wirklich einfach einen Algorithmus,
einen schnellen Algorithmus für Satz bringt, irgendwie in N hoch 3
oder so, dann würde sich die Welt komplett umgraben.
Alles, was quasi schwer ist oder fast alles, was schwer ist an
Optimierungsproblemen, ist dann auf einmal einfach.
Kryptographie würde zusammenbrechen, weil Kryptographie zum Beispiel
darauf basiert, dass Sachen schwer auszurechnen sind.
Wir hätten erstmal ein ganz massives Sicherheitsproblem.
Es gibt aber auch andere Sachen.
Es würden natürlich auch Sachen besser werden dadurch, dass wir
Probleme schneller lösen können als vorher.
Okay, aber es gibt noch andere Szenarien.
Es könnte sein, dass gezeigt wird, dass P gleich NP ist, auch durch
einen polynomiellen Algorithmus für Satz, aber der ist mehr so N hoch
500.
Dann würde gar nicht so viel passieren, weil N hoch 500 ist immer noch
impraktikabel.
Es ist zwar polynomiell, von der theoretischen Sicht ist es ein
himmelweiter Unterschied zwischen exponentiell und polynomiell, aber
in der Praxis ist N hoch 500 einfach das gleiche.
Das geht auch nicht.
Das heißt, das wäre dann in der Theorie ein großes Erdbeben und in der
Praxis würde gar nicht so viel passieren.
Dritte Möglichkeit, es könnte gezeigt werden, dass P gleich NP ist,
auf anderem Wege.
Durch zum Beispiel nicht existenzielle Beweise, sowas wie, es gibt nur
viele Gründe, die dagegen sprechen würden oder so.
Und dann wüssten wir das und wir wären aber keinen Schritt weiter in
der Praxis.
Auf der anderen Seite, was sich auf jeden Fall ändern würde, ist, wenn
jemand zeigt, dass P gleich NP ist, dieser jemand wäre reich und
berühmt.
Ich weiß nicht, ob ich es schon erwähnt habe, es ist wirklich eines
der wichtigsten Probleme auf der Welt.
Es gehört zu den zehn Millenniums-Problemen.
Das heißt, die wurden in Anlehnung an Hilberts-Probleme, die vor 100
Jahren aufgestellt wurden, für die Menschheit in den nächsten 100
Jahren zum lösen, wovon ein paar gelöst wurden, aber nicht viele.
Da hat das Clay-Institut zur Jahrtausendwende zehn Probleme
aufgestellt für die nächsten, ich weiß gar nicht, ob sie das auch
gesagt haben, für die nächsten 100 Jahre oder so.
Und hat als Anreiz auch eine Million Dollar für die Lösung jeden des
beliebigen Problems auf der Liste ausgelobt.
Und P gleich NP oder P ungleich NP ist eins dieser Probleme.
Anders ist sowas wie Riemann-Vermutung oder Goldbach-Vermutung und
sowas sind so die Probleme auf der Liste.
Eins wurde tatsächlich davon gelöst bisher, aber nicht P gleich NP.
Gut,
nochmal zur Zusammenfassung.
Was haben wir gezeigt?
Wir haben den Satz von Cook gezeigt und haben gezeigt, dass Satz NP
schwer ist, sogar NP vollständig, aber insbesondere NP schwer.
Also alles in NP kann mit Satz gelöst werden.
Und dann haben wir andere Probleme, eine ganze Reihe anderer Probleme
kennengelernt und gezeigt, dass die NP schwer sind durch Reduktion.
Und wir haben zum Beispiel Satz auf 3 Satz reduziert, also alles kann
mit 3 Satz gelöst werden.
Dann haben wir 3 Satz auf 3 Color, 3 Color auf Exact Cover und so
weiter.
Und die letzten drei in dieser Vorlesung bis hin zu Knapsack.
Also alles in NP kann mit Knapsack gelöst werden.
So jetzt wollen wir uns ein bisschen entspannen und vielleicht einen
Teil der Vorlesung machen, der jetzt nicht eminent wichtig ist, aber
ich glaube, es ist gut, Ihnen einfach mal so einen Blick über den
Tellerrand zu gönnen.
Wir haben hier natürlich begrenzten Raum und Zeit, um über Sachen zu
reden und da gibt es sehr viel mehr, was sehr interessant ist.
Und diesen Blick über den Tellerrand am Anfang will ich diesen
interessanten Teil ein bisschen erzählen über Entscheidungsprobleme,
die nicht in P oder NP sind.
Und danach werde ich noch ganz kurz was sagen über Probleme, die nicht
Entscheidungsprobleme sind.
Da haben wir ganz am Anfang schon mal darüber geredet, über
Optimierungsprobleme und Optimalwertprobleme, haben dann aber gesagt,
Entscheidungsprobleme sind im Prinzip die einfachsten, deswegen gucken
wir uns die jetzt erstmal an.
Aber gerade für nächste Woche in der Vorlesung werden wir Probleme
angucken, die nicht Entscheidungsprobleme sind.
Deswegen ist es auch wichtig, da ganz am Ende noch mal kurz zuzuhören.
Gut, aber zuerst mal Entscheidungsprobleme.
Es geht nur um Ja oder Nein, ist das Wort in der Sprache oder nicht,
die aber vielleicht nicht in P oder NP sind.
Definitionsnotationelle Sache, um nicht immer die ganze Zeit NP
-Vollständig oder so zu schreiben.
Die Klasse NPC ist das, was ich schon immer rot eingekreist habe, das
sind die NP-Vollständig-Probleme, steht für NP-Complete.
Und NPI steht für NP-Intermediate, sind die Sachen, die sind in NP,
aber nicht in P und nicht NP-Vollständig.
Wir wissen nicht, ob sowas existiert, aber es könnte sein, dass das
eine leere Menge ist, aber wenn es nicht eine leere Menge ist, dann
sind das die Probleme, kann ja sein, irgendwas, was nicht polynomiell
gelöst werden kann, aber trotzdem nicht stark genug ist, um alles zu
lösen.
Das ist NP-Intermediate.
Es gibt den Satz jetzt von Ladner, wenn P ungleich NP ist, dann gibt
es NP-Intermediate-Probleme.
Und das ist auch wirklich, das ist nicht so unwahrscheinlich, also wir
gehen davon aus, dass in P haben wir sowas wie polynomiale Laufzeit,
NP -Vollständig haben wir exponentielle Laufzeit und dazwischen hätten
wir sowas wie sub-exponentielle Laufzeit, sowas wie N hoch Log-Star-N
oder so.
So sieht jetzt das Bild aus.
Wir haben hier ganz viel über den roten Bereich geredet, die NPC.
Wir haben wenig über die Klasse P geredet und dazwischen, dieser
Zwischenraum ist sozusagen NP-Intermediate.
Das beantwortet sozusagen die Frage, was ist dazwischen so ein
bisschen.
Naja, wir vermuten, dass es so aussieht.
Also die ganzen Bilder, die ich hier zeige, sind immer die
Vermutungen.
Es könnte sein, dass es alles kollabiert und eigentlich alles nur P
ist.
Und der ganze alles außerhalb von P ist eigentlich leer.
Um jetzt Sachen mal zu zeigen, die nicht in NP sind, wo uns einfach
fragen, wo das Orakel uns keinen geeigneten Hinweis geben kann, den
wir schnell verifizieren können.
Wie sieht so ein Problem aus?
Da ist es das Erste, was man tut, ist sich Komplementsprachen
angucken.
Also bleiben wir mal bei P erstmal.
CoP ist die Klasse der Sprachen, deren Komplement in P ist.
Also ich nehme einfach eine Sprache, die ist in P und dann einfach
sage ich, da sind ja gewisse Wörter aus dem Alphabet und sage ich
einfach Komplement davon.
Also die Wörter, die nicht in der Sprache sind.
Oder CoNP ist, naja, ich nehme eine Sprache, die ist in NP und ich
sage die Wörter, die nicht in dieser Sprache sind.
Was wir wissen und was relativ leicht ist, P ist gleich CoNP, äh CoP,
Gott, P ist gleich CoP.
Weil wir für P haben wir einen polynomiellen Entscheider,
deterministisch, sagt er zu jeder Eingabe Ja oder Nein, ohne Orakel.
Und dann können wir einfach die Turing-Maschine nehmen und Ja in Nein
ändern und Nein in Ja ändern, ansonsten tut das Ding das gleiche.
Also dann können wir auch die Nein-Instanzen einfacher kennen.
Wenn wir die Ja-Instanzen von den Nein-Instanzen trennen können,
können wir die Nein-Instanzen einfacher kennen.
Das ganze Ding ist jetzt, CoP ist enthalten in CoNP, so wie P in NP
enthalten ist.
Sie müssen sich vorstellen, CoNP ist jetzt, ich möchte Nein-Instanzen
erkennen.
Und da ist es nicht so klar, ob das jetzt gleiche ist wie NP.
Weil dieses Orakel, was wir uns angeguckt haben, das hat uns immer nur
Hinweise für Ja-Instanzen gegeben, gibt uns aber für Nein-Instanzen
nichts.
Das ist so eine Asymmetrie drin.
Also die Frage ist, und die ist tatsächlich offen, ob NP gleich CoNP
ist.
Wenn wir ein Orakel für Ja-Instanzen haben, haben wir dann auch ein
Orakel für Nein-Instanzen.
Ist nicht so klar, wir machen gleich ein Beispiel.
Wenn die beiden unterschiedlich sein sollten, dann würde das auch
lösen, dass P und gleich NP ist.
Und das ist auch die allgemeine Vermutung, dass die beiden
unterschiedlich sind.
Also ist aber schwieriger zu zeigen sozusagen, als die P und gleich NP
Vermutung.
Wenn die beiden jetzt gleich sein sollten, ist nicht so klar, was
passieren würde.
Es ist dann nicht automatisch, dass P gleich NP ist.
Also es wäre möglich, dass die beiden gleich sind und trotzdem P und
gleich NP ist.
Also wie sieht es aus?
Die grüne Klasse ist jetzt hier diese CoNP-Klasse.
Die hat CoP drin, was ja das gleiche ist wie P. Und die sitzt hier
dazwischen.
Die kann nicht dieses Ding hier enthalten, wie wir gleich sehen
werden.
Machen wir mal ein Beispiel.
CoTSP.
TSP, erinnern Sie sich, war diese Tour.
Gibt es eine Tour der Länge höchstens K durch alle Knoten?
Und jetzt fragen wir, ob das eine Nein-Instanz ist.
Also die Frage, die wir uns stellen als Entscheidungsproblem, gibt es
keine Tour der Länge höchstens K.
Und stellen Sie sich vor, das ist eine Ja-Instanz zu diesem CoTSP
-Problem.
Es gibt also wirklich keine Tour der Länge höchstens 100.
Wie sollte uns das Orakel davon überzeugen?
Was sollte das Orakel da hinschreiben, um uns davon zu überzeugen,
dass es tatsächlich keine Tour gibt der Länge höchstens K?
Also wir vermuten, dass CoTSP nicht in NP ist.
Dass das Orakel uns Ja-Instanzen von CoTSP keine Hinweise geben kann,
die wir schnell verifizieren können.
CoTSP ist aber in NP, weil das Orakel uns von einer Nein-Antwort ganz
leicht überzeugen kann.
Eine Nein-Antwort heißt, das stimmt nicht, dass es keine Tour der
Länge kleiner gleich K gibt.
Also das Orakel gibt uns einfach eine Tour, die hat eine Länge kleiner
gleich K und damit wissen wir okay, das ist eine Nein-Antwort.
Vielleicht denken sie einmal kurz nach über Primzahltest.
Die Frage ist, ist eine gegebene Zahl eine Primzahl?
Wie werden sie von einer Ja-Antwort überzeugt?
Nicht so einfach.
Wie werden sie von einer Nein-Antwort überzeugt?
Ziemlich einfach.
Sie kriegen zwei Faktoren, die zusammen diese Zahl ergeben.
Das können sie nachrechnen.
Also Primzahltest ist in CoNP ziemlich leicht.
Das heißt, hier hätten wir dieses Problem CoTSP.
Wir vermuten, es liegt da draußen außerhalb von NP.
Jetzt hier, der Zwischenraum ist nicht so ganz klar.
Es gibt das folgende Lemma.
Wenn etwas NP vollständig ist und in CoNP, also wenn es in Rot und in
Grün liegt, dann wäre NP gleich CoNP.
Und der Beweis ist wieder analog zu den anderen Sachen.
Also sage ich so eine Sprache, die ist in CoNP und NP vollständig,
dann existiert eine polynomiale nicht-deterministische Turing-Maschine
für die Komplementsprache.
Also ein Orakel, was uns Nein-Antworten gibt.
Auf der anderen Seite können wir jede Sprache in NP auf L reduzieren.
Also können wir auch die Nein-Antwort von den anderen Sprachen mit
einem Orakel klassifizieren.
Wir haben diese Transformation, eine andere Sprache und da ist Ja
genau dann, wenn Ja.
Also auch Nein genau dann, wenn Nein.
Und wenn wir das gemacht haben, dann können wir jetzt das Orakel nach
dem Nein fragen.
Dann gibt es ein kurzes Orakel Nein dort.
Das heißt, die andere Sprache wäre dann auch in CoNP.
Das heißt, dann wäre NP gleich CoNP.
Also wenn das wirklich so ist, dass NP ungleich CoNP ist, was wir
vermuten, dann heißt es also, dass CoNP und NP complete nichts
gemeinsam haben können.
Das heißt auch, dass wenn wir ein Problem haben, was in NP ist und in
CoNP, also Ja-Antworten können leicht verifiziert werden, Nein
-Antworten können leicht verifiziert werden, dann ist das Problem
entweder ganz leicht, oder es ist NP-intermediate.
Das heißt, das akkurate Bild wäre eigentlich das hier.
NP-intermediate ist genau dieser Schnitt von diesem CoNP und NP ohne
das Blaue.
Da gibt es nichts dazwischen.
Also das ist irgendwie immer so ein Test, wenn Sie sich fragen, ob Ihr
Problem eventuell NP-vollständig ist, bevor Sie jetzt irgendwie will,
darauf losraten, eine Reduktion zu machen.
Geht natürlich auch.
Das, was ich immer tue, ist, ich frage mich, liegt es denn vielleicht
in dem Grün?
Also ich habe ein Problem, dass ich Ja-Antworten leicht verifizieren
kann, geht meistens einfach.
Das haben wir schon häufig jetzt gemacht.
Und fragen Sie sich, kann ich mich leicht von einer Nein-Antwort
überzeugen?
Gibt es ein Orakel für eine Nein-Antwort, eine leichte?
Okay.
Und wenn das der Fall ist, dann sind Sie also in dem grünen Bereich
und dann wird es wahrscheinlich nicht NP-vollständig sein.
Ja.
Okay.
So, machen wir das noch ein bisschen weiter.
Das ist hier ein Subgraph Isomorphie.
Also Sie fragen sich vielleicht, kann ich Ihnen ein Problem geben, was
dort drin liegt?
Vermutlich, ja, kann ich.
Und das ist Subgraph Isomorphie, das ist so der kanonische Kandidat.
Also was ist das?
Wir haben G und H, das sind zwei Graphen.
H ist der kleine, G ist der große.
Und die Frage ist, finde ich eine Kopie von H in meinem G?
Gibt es da diesen Isomorphismus, der sagt einfach, welche Knoten von H
entsprechen welchen Knoten von G?
Also ist H Isomorph zu einem Subgraph von G?
Das ist ein schwieriges Problem.
Wir kennen keinen Polynomialzeitalgorythmus dafür.
Ja-Antwort ist leicht zu verifizieren.
Wir kriegen so einen Isomorphismus und müssen einfach nur gucken, ja
stimmt, das ist H in G.
Nein-Antworten sind auch leicht zu verifizieren.
Kann ich Ihnen aber nicht sagen, warum.
Genau, das ist ein Problem, was wahrscheinlich in NP-Intermediate ist.
Tatsächlich... ach nee, oh Gott, ich erzähle Quatsch.
Subgraph-Isomorphie ist NP-Vollständig.
Das ist ein rotes Problem.
Aber wenn ich Graph-Isomorphie mache, wenn beide Graphen gleich groß
sind und die Frage ist, ist es der gleiche Graph?
Ist es der gleiche Graph?
Dann nur irgendwie, dass die Knoten anders benannt sind.
Einfach nur benennen die Knoten anders um.
Guck mal, der hier ist der hier und der hier ist doch der hier und das
ist doch eigentlich der gleiche Graph.
Das Problem Graph-Isomorphie, das ist wahrscheinlich NP-Intermediate.
Also sind die beiden Graphen Isomorph, also Isomorph heißt einfach nur
der gleiche Graph bis auf Umbenennen der Knoten.
So, jetzt habe ich es richtig.
Also Graph-Isomorphie, Subgraph-Isomorphie ist da oben in dem roten,
Graph -Isomorphie ist hier in dem grünen.
Das ist das Problem, was wahrscheinlich NP-Intermediate ist.
Es wurde vor ein paar Jahren mal angekündigt, dass jemand einen sub
-exponentiellen Algorithmus hat für Graph-Isomorphie.
Also im Moment ist das Beste, was man machen kann, ist einfach alles
ausprobieren.
Alle Bezeichnungen auf beiden Seiten ausprobieren und dann gucken, ob
es stimmt.
Und sub-exponentiell ist so ein N hoch, Lockstar-N oder sowas.
Jetzt genau, was ist noch außerhalb von denen.
Das ist immer noch alles mit Orakel-Turing-Maschinen relativ einfach
in den Griff zu kriegen.
Ich möchte Ihnen kurz etwas erzählen von der polynomiellen Hierarchie,
einfach damit Sie es mal gehört haben.
Und zwar das folgende.
Wir betrachten eine Variante von SAT.
SAT, so wie Sie es kennen, ist einfach U ist eine Menge von Variablen
und C ist eine Menge von Klauseln.
Und die Frage ist, können die Variablen so belegt werden mit
Wahrheitswerten, dass alle Klauseln erfüllt sind.
Jetzt stellen Sie sich vor, die Variablen kommen in zweierlei Arten.
Es gibt die U1-Variablen und die U2-Variablen.
Das ist vornherein klar.
Und jetzt stellen Sie sich vor, es gibt jemanden, der die U1-Variablen
kontrolliert und jemanden, der die U2-Variablen kontrolliert.
Die U1 werden zuerst kontrolliert und zwar für die U1 wird eine
clevere Wahrheitsbelegung T1 gewählt, sodass der böse Gegenspieler,
der U2 kontrolliert, das nicht mehr kaputt machen kann.
Sodass egal, wie der andere seine Variablen jetzt belegt, alle
Klauseln bleiben erfüllt.
Also wir finden eine Wahrheitsbelegung für U1.
Das ist irgendwie, was wir zur Verfügung haben, sodass danach für U2
gemacht werden kann, was wolle.
Es bleibt erfüllt alles.
Das ist auch ein Problem, das ist nicht so einfach für einen Orakel
uns zu sagen.
Ich meine, das Orakel kann uns natürlich sagen, wie wir U1 belegen
sollten.
Aber wie wollen wir jetzt verifizieren in polynomialzeit, dass das das
Gewünschte tut?
Dass egal, wie U2 gemacht wird, das erfüllbar bleibt.
Das können wir nicht in polynomialzeit verifizieren.
Und das Orakel kann uns auch nicht so richtig einen Tipp geben, warum
das so sein sollte.
Stellen Sie sich zum Beispiel auch vor, U1 ist leer.
Alle Variablen sind rot.
Dann ist die Frage, ist diese Klauselmenge so, dass egal, wie die
Wahrheitsbelegungen gemacht werden, es eh immer erfüllt?
Das ist ein schwieriges Problem, das zu sehen, dass diese Klauseln,
egal wie die belegt werden, immer erfüllt wird.
Das ist ein CoNP Problem, was nicht in NP ist wahrscheinlich.
Okay, also dieses Problem bezeichnen wir auch als Quantified
Satifiability 2 oder auch Exist for All Sat.
Es existiert für die grünen, so dass für alle roten.
Und warum stoppen?
Wir können jetzt auch Quantified Satifiability 3 angucken, also Exist
for All Exists.
Es gibt jetzt grüne, rote und blaue Variablen.
Wir müssen die grünen belegen, so dass für alle Belegungen der roten.
Es existiert noch eine Belegung der blauen, so dass alle Klauseln
erfüllt sind.
Oder Quantified Satifiability 4.
Exist for All Exists for All Sat.
Und so weiter.
Und das ist die polynomielle Hierarchie, sozusagen.
Das ist jetzt ein Problem und keine Klasse von Problemen, aber das ist
sozusagen Repräsentanten, was sie sich darunter vorstellen müssen.
Also das normale Sat ist einfach nur Exist Sat.
Dann ist Exist for All Sat, Exist for All Exist Sat, Exist for All,
Exist for All Sat und so weiter.
Das ist eine ganze Hierarchie und alle Probleme, die da drin, die mit
so einer, mit alternierenden Krantoren Sat-Formel dargestellt werden
kann, die heißen in ph.
Bemerkung, genau.
Exist Sat ist vollständig für np, also ist np vollständig, haben wir
ja gesehen.
For All Sat, was ich gesagt habe, wenn es keine grünen Variablen gibt,
nur rote, entscheide, ob die Formel immer erfüllt ist, egal wie die
Wahrheitsbelegung gemacht wird, ist Co-np vollständig.
Ich kann zum Beispiel Co-tsp so darstellen.
So, wie sieht das in diesem Bild jetzt hier aus?
Also die polynomielle Hierarchie ist eine unendliche Menge von
Klassen.
Die werden so hier bezeichnet, Sigma 2p, np ist Sigma 1p und Sigma 2p
enthält dann schon alles hier.
Und dann gibt es Sigma 3p, Sigma 4p, Sigma... bis und zu unendliche.
Und die Vereinigung von all denen ist die Klasse ph, Polynomial
Hierarchie.
Da außen drum gibt es jetzt noch die Klasse p-Space.
Das sind Probleme, die können in polynomialen Platz gelöst werden von
der Turing-Maschine, deterministisch.
Die Zeit ist uns egal, nur dass das Band ist nur polynomial groß.
Und da kann die Turing-Maschine so lange machen, wie sie will.
Das ist p-Space.
Da kann sie das ausprobieren mit dieser Polynomial Hierarchie.
Das sind so Sachen, auch in p-Space, das sind so Sachen, die sind wie
Spiele mit zwei Spielern.
Der Exist-Spieler und der For-All-Spieler.
Und die Frage ist, gewinnt der Exist-Spieler?
Er macht seinen ersten Zug, er setzt für U1 die Wahrheitswerte, dann
ist der Gegenspieler dran, der setzt für U2 die Wahrheitswerte.
Fies.
Dann sind wir wieder dran als Exist-Spieler, wir setzen für U3 die
Wahrheitswerte.
Gut.
Unser Ziel ist es, die Klauseln alle zu erfüllen und vom Gegenspieler
das Ziel ist, mindestens eine Klausel nicht zu erfüllen.
Und da sind so ganz viele Spiele drin, also Schach-Auffall,
Gemeinheiten, Brettern ist p-Space-Complete und so ein Zeug.
Gut.
Außerhalb von p-Space gibt es Exp-Time.
Da ist uns der Platz egal, die Laufzeit soll aber höchstens
exponentiell sein.
Da gibt es noch mehr Klassen, erzähle ich jetzt nicht.
Ich will bloß noch einmal sagen, wir sind natürlich immer noch
innerhalb der entscheidbaren Sprachen hier.
Das heißt außerhalb von denen gibt es natürlich noch die semi
-entscheidbaren Sprachen und dann sind wir wirklich bei allen formalen
Sprachen.
Also das ist nur so ein bisschen eine Perspektive.
Wir interessieren uns jetzt hier in der Vorlesung vor allen Dingen für
den roten Bereich.
Testen Sie sich.
Ja, Ihre Aufgabe ist, vielleicht gucken Sie mal rein in diesen Quanta
-Artikel, a short guide to hard problems, wo für den allgemeinen
Laien, der ein bisschen naturwissenschaftlich interessiert ist, ein
bisschen aufgezählt wird, wie die verschiedenen Komplexitätsklassen
aussehen.
Quanta führt nicht alle von denen an, die ich hier angeführt habe.
Auf der anderen Seite führen die noch andere an, die ich hier nicht
erwähnt habe und erzählt ein bisschen so wirklich high level, was das
heißt.
Auch was wie zum Beispiel Quantum Computing da drin ist oder
probabilistische Algorithmen da rein passen.
Also wenn Sie Lust haben, schauen Sie einfach mal rein auf Quanta
Magazine.
Die haben dieses Jahr im Sommer diesen schönen kleinen
Übersichtsartikel geschrieben.
Ist nicht lang.
Gut.
So, das war der Teil, der wirklich nur zu Entscheidungsproblemen war.
Die Fragen, die wir uns da immer gestellt haben, ist immer nur Ja,
Nein.
Egal ob das jetzt Exponential Time oder PSPACE war oder die Hierarchy
oder so, das war nur Ja-Nein-Fragen.
Natürlich, wenn Sie ganz konkret Probleme bearbeiten und Algorithmen
dafür entwerfen sollen, ist es in den seltensten Fällen eine Ja-Nein
-Frage, die Sie da entscheiden wollen.
In den meisten Fällen wollen Sie irgendeine Art von Ausgabe.
Sie wollen nicht nur wissen, ob es eine Tour der Länge höchstens K
gibt, sondern Sie hätten gerne die Tour.
Sie wollen nicht nur wissen, ob der Dieb eine Auswahl von Gegenständen
treffen kann, die er mitnimmt.
Sie hätten dann auch gerne gewusst, welche Gegenstände er mitnehmen
soll.
Wir haben schon am Anfang einmal darüber geredet, ich glaube, das war
auch mit TSP, dass man, wenn man die Ja-Nein-Frage entscheiden kann,
manchmal auch das Glück hat, die entsprechenden Fragen nach dem
Optimalwert oder nach dem Optimum zu lösen durch so Tricks, durch
wiederholtes Aufrufen von so einem Ja-Nein-Algorithmus.
Aber zumal wir nächste Woche wirklich auch für Nicht
-Entscheidungsprobleme uns was angucken wollen, will ich hier noch
einmal ganz kurz erwähnen, was es da noch so gibt.
Also es gibt sogenannte Suchprobleme.
Suchprobleme sind ähnlich wie Entscheidungsprobleme gegeben als eine
Menge von Instanzen.
Stellen Sie sich vor, Graphen mit Gewichtsfunktion oder
Gegenstandsmengen mit Gesichtsfunktion.
Und es gibt dann, jede Instanz hat eine gewisse Art von Lösung.
Eine Tour, die nicht zu lang ist oder eine Auswahl von Gegenständen,
die nicht zu schwer sind, aber viel Kosten haben.
Oder eine Möglichkeit, wie man das auf die Waage tun kann, dass die
ausgeglichen ist.
Oder eine Dreifärbung für den Graphen und so weiter.
Eine gewisse Menge von Lösungen.
Und S und ein Pi von I ist die Menge aller Lösungen.
Und bisher haben wir uns immer nur um die Frage gekümmert, ist diese
Menge hier leer oder nicht.
Oder ist da mindestens eine Lösung drin.
Das war nur die einzige Frage.
Und bei dem Suchproblem ist jetzt auch gegeben die Instanz, gut wenn
es leer ist, dann müssen wir das auch erkennen.
Und wenn es aber nicht leer ist, dann würden wir auch gerne mindestens
ein Element, welches ist uns egal, ein beliebiges Element aus der
Lösungsmenge haben, als Output.
Man kann das alles formal machen, indem die Turing-Maschine das auf
das Band schreibt und dann stoppt und dann wir das Band auslesen und
das ist eine geeignete Kodierung von Lösungen und so weiter.
Machen wir jetzt nicht.
Ich überlasse Ihnen sozusagen die Denkarbeit ein bisschen.
Das geht alles analog, so wie Sie sich das vorstellen.
Machen wir mal kurz ein Beispiel.
TSP, zwei verschiedene Varianten von Suchproblemen.
Das eine ist, gib eine optimale Tour an.
Wir haben da nicht mehr Fragen, ja, nein Fragen, sondern Aufgaben.
Wir müssen irgendwie was zurückgeben.
Und dann wäre diese Menge S, die Solution, S steht für Solution, die
Lösungsmenge, ist die Menge aller optimalen Touren.
Die ist, solange es irgendeine Tour gibt, ist die Menge nicht leer und
da sind aber nur die kürzesten drin.
Und wir wissen noch nicht mal, welchen Wert die kürzesten haben.
Das sind die kürzesten.
In Variante zwei haben wir noch diesen Parameter k gegeben und sagen,
okay, in der Lösungsmenge sind alle Touren, die höchstens k lang sind.
Die müssen nicht unbedingt die kürzesten sein, solange sie höchstens k
lang sind.
Und dann ist also S, Pi von g zu einem gegebenen Graphen g, ist die
Menge aller Touren, die Länge höchstens k haben.
Okay, das wären also Suchprobleme.
Dann gibt es noch den Hamilton-Kreis.
Das ist ein ganz bekanntes Suchproblem.
Also ein Hamilton-Kreis in einem Graphen ist eine zyklische
Permutation der Knoten, die irgendwie benachbart in der Permutation
sind durch eine Kante im Graphen benachbart.
Das heißt, es ist überhaupt möglich in dem Graphen in einem Kreis zu
laufen und jede Stadt zu jedem Knoten genau einmal zu besuchen, egal
wie lang das ist.
Also es gibt keine Längen auf den Kanten, sondern einfach nur, ist es
denn überhaupt möglich, ohne durch durch den Knoten zweimal
durchzugehen, alles aufzusammeln in einem Kreis.
Das ist einfach Hamilton-Kreis.
Okay, und das Hamilton-Kreis-Suchproblem sagt dann einfach gegeben den
Graphen, ungewichtet, ungerichtet, gib einen Hamilton-Kreis an, falls
einer existiert oder halt nicht.
Statt nur zu sagen, es existiert ein Hamilton-Kreis, ich hätte gerne
einen, wenn er wirklich existiert.
So, bei Suchproblemen kann man jetzt ganz ähnlich wie zu
Entscheidungsproblemen eine ganze Menge Sachen machen.
Wir können eine Orakel-Turing-Maschine uns analog eine Variante
definieren, die jetzt, die muss uns jetzt nicht nur verraten, ob die
Lösung ja oder nein ist, sondern sie muss uns auch noch einen Hinweis
geben, wie eine Lösung aussieht, die wir dann in polynomialer Zeit
verifizieren und ausgeben können.
Dann kriegen wir analog mit dieser neuen Turing-Maschinen-Definitionen
kriegen wir eine Klasse NP auf den Suchproblemen, die also polynomiale
Zeit brauchen für so eine Orakel-Turing-Maschine.
Wir kriegen analog eine Klasse P, die von der deterministischen Turing
-Maschine die richtige Funktion realisieren, also die richtigen Output
liefern.
Und dann gibt es analog den Begriff der NP-Schwere.
Da müssen wir dann bei den Reduktionen, müssen wir aufpassen, das sind
nicht die Reduktionen, die wir kennengelernt haben, die sind ein
bisschen anders.
Sogenannte Turing-Reduktionen haben auch ein anderes Zeichen, hier mit
einem T unten dran, weil wir auch wollen, nicht nur Ja-Instanz ist
genau dann Ja-Instanz, sondern wir finden eine Lösung des
Suchproblemes, wenn wir hier eine Lösung des Suchproblemes finden,
also wir brauchen mit Lösung.
Und die Frage, ob P gleich NP ist in dieser Welt der Suchprobleme, ist
genauso offen.
Also wir können davon ausgehen, zumindest soweit ich das weiß, wenn
das Entscheidungsproblem schwer ist, dann ist das Suchproblem erst
recht schwer.
Das Suchproblem ist schwieriger.
Und ich kenne, kenne ich irgendwas?
Ich kenne auch nichts, wo das Suchproblem irgendwie schwerer ist als
das Entscheidungsproblem.
Glaube ich, da könnte ich aber... also es ist so quasi das Gleiche.
Also Travelling Salesman, Hamilton Kreis, die ganzen Suchprobleme,
wenn die Entscheidungsprobleme schwer sind, sind die Suchprobleme auch
schwer.
Gut.
Hier Hamilton Kreis und TSP sind ganz explizit genannt als
Suchprobleme, die NP schwer sind.
So, dann gibt es noch eine andere Art von Problemen, wo die Ausgabe
ist eine Zahl.
Und das ist nicht eine Zahl so wie die Länge von Natur, sondern das
ist die Anzahl der Lösungen.
Wir interessieren uns nicht dafür, ob es einen Hamilton Kreis gibt.
Wir interessieren uns nicht dafür, einen bestimmten Hamilton Kreis zu
finden, sondern wir interessieren uns dafür, wie viele Hamilton Kreise
es gibt.
Also die Ausgabe ist einfach nur eine Zahl.
Es ist einfach die Kardinalität dieser Menge.
Wieder völlig unklar, wie uns ein Orakel kann uns natürlich diese Zahl
verraten, aber wie soll sie uns davon überzeugen, dass es die exakt
richtige Zahl ist.
Das Orakel, wenn man jetzt irgendwie die Platzrestriktion und die
Zeitrestriktion wegnimmt, selbst wenn uns das Orakel alle Lösungen
hinschreibt, was ja schon zu viel wäre für polynomiale Zeit meistens,
wie kann es uns davon überzeugen, dass das alle sind und irgendwie
nichts vergessen wurde.
Aufzählprobleme sind beispielsweise Hamilton Kreis Aufzählprobleme.
Wie viele Hamilton Kreise gibt es denn im Graphen G?
Das ist natürlich schwieriger als zu entscheiden, gibt es einen
Hamilton Kreis oder nicht.
Wenn die Zahl, die da rauskommt, positiv ist, dann gibt es wohl einen
und wenn die Zahl null ist, dann gibt es wohl keinen.
Das ist auch noch schwieriger als zu entscheiden, finde einen Hamilton
Kreis.
Diese Aufzählprobleme sind wirklich notorisch schwer.
Die sind nicht zu machen.
Also von denen sollte man wirklich die Finger lassen.
Ein berühmtes Beispiel ist die Permanente einer Matrix.
Das ist so ähnlich wie die Determinante.
Die Determinante ist ja auch so eine Summe über verschiedene
Permutationen und dann immer so minus 1 hoch irgendwas.
Und die Permanente ist das gleiche, bloß dass dieses minus 1 hoch
irgendwas weg ist.
Da wird immer plus, plus, plus, plus, plus, plus gerechnet.
Das ist, oder wenn Sie sich mit Graphen auskennen, das ist das gleiche
wie die Anzahl der perfekten Matchings in bipartiten Graphen.
Das ist ein Problem, also das ist diese Permanente einer Matrix oder
Anzahl der perfekten Matchings, das ist vollständig für die
entsprechende Klasse der Aufzählprobleme, Sharp P heißen die.
Das ist Sharp P vollständig.
Und dann gibt es so Sachen wie der Satz von Toda, der sagt, wenn ich
ein Problem habe in polynomial hierarchy, also zum Beispiel so ein
Spiel mit den beiden Spielern, die diese Klauseln erfüllen oder nicht
erfüllen wollen, der eine Spieler versucht sie zu erfüllen, der andere
Spieler versucht sie nicht zu erfüllen.
Also exist for all, exist for all, exist for all und so weiter.
Jedes so ein Problem kann man lösen, das ist ein Entscheidungsproblem,
durch den Aufruf eines einzelnen Sharp P vollständigen Problems.
Indem ich in einem anderen Problem was zähle.
Und das ist der Satz von Toda.
Also diese Sharp P ist wirklich, also das ist out of reach, da
brauchen wir uns nicht so mit befassen.
Okay, so das war es von heute.
Ich möchte noch ganz kurz sagen, es gibt natürlich noch mehr Probleme
als die, die wir hier besprechen.
Es gibt natürlich so eine Sachen wie, was ist das Integral von Sinus x
dx, unbestimmtes Integral.
Wie soll uns jemand davon überzeugen.
Und das ist auch, das zählt nichts, das gibt keine Lösung, sondern...
Gut, aber wir bleiben bei unseren kombinatorischen Sachen.
Aufzählprobleme haben sie heute nur einmal kurz kennengelernt, werden
wir nicht wieder finden.
Aber Probleme, wo die Frage nach einer Zahl gestellt ist, werden wir
uns nächste Woche angucken.
Vielen Dank.