NP-vollständig/NPC

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

NP-vollständig/NPC

Beitrag von SophiaLi1 » 21. Sep 2017 11:09

Hallo,

ich habe verstanden, was Probleme der Klasse P und Probleme der Klasse NP sind. Leider fällt mir das bei dem Verständnis der Klasse NPC schwerer.

Meine Fragen:
1) Was bedeutet es genau, wenn ein Entscheidungsproblem in NPC (= "NP-vollständig") ist? Wie kann ich das überprüfen?
2) Was bedeutet es, wenn ein Entscheidungsproblem "NP-schwer" ist?
3) Warum spricht man explizit nur von Entscheidungsproblemen und nicht allgemein von Problemen?
4) Da sowohl P eine Teilmenge von NP ist als auch NPC eine Teilmenge von NP: Gibt es Entscheidungsprobleme, die in NP, aber weder in P noch in NPC sind?

Vielen Dank!

goerlibe
Mausschubser
Mausschubser
Beiträge: 51
Registriert: 24. Apr 2017 19:22

Re: NP-vollständig/NPC

Beitrag von goerlibe » 21. Sep 2017 12:09

Vielleicht hilft dir das Video :wink:

https://www.youtube.com/watch?v=YX40hbAHx3s&t=1s

zu 3)
du kannst ein beliebiges Problem als Entscheidungsproblem formulieren, das eigentliche Problem ist dann mindestens so kompliziert wie das Entscheidungsproblem

zu 4)
das ist eine der großen ungelößten Fragen der Informatik, siehe Video (da gab es erst letztens Aufregung, weil (Prof. Dr. Doz. oder was auch immer der für Titel hat) Norbert Blum meinte, einen Beweis für P != NP zu haben, leider war ein Fehler im Beweis)

Hans123
Mausschubser
Mausschubser
Beiträge: 44
Registriert: 12. Jun 2017 13:23

Re: NP-vollständig/NPC

Beitrag von Hans123 » 21. Sep 2017 13:15

Zu 4) Man kennt keine solcher Probleme. Allerdings so wie wir das gelernt haben, müsste eigentlich NP = NPC gelten, wenn ich keinen Denkfehler habe. Da ja X in NPC ist, wenn man alle Probleme in NP auf X polynomiell reduzieren kann, kann ich ja jedes Problem Y in NP auf X reduzieren und bin dann automatisch in NPC.

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: NP-vollständig/NPC

Beitrag von SophiaLi1 » 21. Sep 2017 14:11

Hans123 hat geschrieben:
21. Sep 2017 13:15
Allerdings so wie wir das gelernt haben, müsste eigentlich NP = NPC gelten, wenn ich keinen Denkfehler habe. Da ja X in NPC ist, wenn man alle Probleme in NP auf X polynomiell reduzieren kann, kann ich ja jedes Problem Y in NP auf X reduzieren und bin dann automatisch in NPC.
Das hat mich auch verwirrt. Laut Folien ist die Definition von NPC:
Ein Entscheidungsproblem X in NP ist auch in NPC, wenn alle Probleme in NP sich auf X polynomiell reduzieren lassen.
Vielleicht verstehe ich den Satz auch einfach nicht. :?:

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: NP-vollständig/NPC

Beitrag von Prof. Karsten Weihe » 23. Sep 2017 08:22

SophiaLi1 hat geschrieben:
21. Sep 2017 14:11
Ein Entscheidungsproblem X in NP ist auch in NPC, wenn alle Probleme in NP sich auf X polynomiell reduzieren lassen.
Vielleicht verstehe ich den Satz auch einfach nicht. :?:
NPC ist eine Teilmenge von NP. Ich betrachte ein festes Problem X in NP, zum Beispiel TSP. Wenn ich beweisen kann, dass sich jedes Y in NP polynomiell auf X reduzieren kann, dann habe ich bewiesen, dass X in NPC ist.

Sollte ich X in NPC für ein polynomiell lösbares Problem beweisen können, dann habe ich damit auch P = NP bewiesen.

Intuitiv formuliert: Die Probleme in P sind in gewisser Weise die "einfachsten" in NP, die Probleme in NPC sind die "schwersten". Und wenn ein einfachstes zugleich ein schwerstes ist, dann ist alles gleich schwer.

So herum klarer?

KW

Benutzeravatar
SophiaLi1
Kernelcompilierer
Kernelcompilierer
Beiträge: 542
Registriert: 5. Jan 2014 11:48

Re: NP-vollständig/NPC

Beitrag von SophiaLi1 » 23. Sep 2017 11:33

Von meinem Verständnis war ich bisher auch so weit. Was mir bis jetzt noch fehlt, ist (polynomielle) Reduktion zu verstehen. Was bedeutet es, ein Problem auf ein anderes zu reduzieren? Besonders im Bezug auf Entscheidungsprobleme ist mir das noch nicht klar. Am besten wäre hierfür ein einfaches Beispiel. Hätten Sie hierfür eins?

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: NP-vollständig/NPC

Beitrag von Prof. Karsten Weihe » 23. Sep 2017 11:51

SophiaLi1 hat geschrieben:
23. Sep 2017 11:33
Am besten wäre hierfür ein einfaches Beispiel. Hätten Sie hierfür eins?
Sie finden ein paar Beispiele auf den letzten Folien von "Algorithmische Komplexität", alles ab SAT.

Ein Entscheidungsproblem X auf ein Entscheidungsproblem Y polynomiell zu reduzieren, heißt generell: Es gibt einen polynomiellen Algorithmus, der jede Instanz I_X von X in eine Instanz I_Y von Y transformiert, so dass gilt: I_X ist eine Ja-Instanz <=> I_Y ist eine Ja-Instanz.

Daraus folgt dann logisch zwingend: Wenn Y polynomiell lösbar ist, dann ist auch X polynomiell lösbar, nämlich über diesen "Umweg" via Y.

KW

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: NP-vollständig/NPC

Beitrag von Prof. Karsten Weihe » 23. Sep 2017 11:55

Prof. Karsten Weihe hat geschrieben:
23. Sep 2017 11:51
SophiaLi1 hat geschrieben:
23. Sep 2017 11:33
Am besten wäre hierfür ein einfaches Beispiel. Hätten Sie hierfür eins?
Sie finden ein paar Beispiele auf den letzten Folien von "Algorithmische Komplexität", alles ab SAT.

Ein Entscheidungsproblem X auf ein Entscheidungsproblem Y polynomiell zu reduzieren, heißt generell: Es gibt einen polynomiellen Algorithmus, der jede Instanz I_X von X in eine Instanz I_Y von Y transformiert, so dass gilt: I_X ist eine Ja-Instanz <=> I_Y ist eine Ja-Instanz.

Daraus folgt dann logisch zwingend: Wenn Y polynomiell lösbar ist, dann ist auch X polynomiell lösbar, nämlich über diesen "Umweg" via Y.

(Genau gesagt muss für den letzten Satz noch zusätzlich argumentiert werden: Da die Transformation polynomiell ist, muss die Größe von I_Y polynomiell in der Größe von I_X bleiben, d.h. wenn der Lösungsalgorithmus für Y polynomiell in der Größe der Instanz I_Y ist, dann sind Transformation plus Lösungsalgorithus zusammen polynomiell in der Größe von I_X, da sowohl Polynom plus Polynom als auch Polynom mal Polynom jeweils wieder ein Polynom ergibt.)

KW

nozyde
Erstie
Erstie
Beiträge: 20
Registriert: 7. Jun 2017 21:22

Re: NP-vollständig/NPC

Beitrag von nozyde » 24. Sep 2017 17:03

SophiaLi1 hat geschrieben:
23. Sep 2017 11:33
Von meinem Verständnis war ich bisher auch so weit. Was mir bis jetzt noch fehlt, ist (polynomielle) Reduktion zu verstehen. Was bedeutet es, ein Problem auf ein anderes zu reduzieren? Besonders im Bezug auf Entscheidungsprobleme ist mir das noch nicht klar. Am besten wäre hierfür ein einfaches Beispiel. Hätten Sie hierfür eins?
Entscheidungsprobleme:
Wenn man die Komplexität von Problemen betrachtet gibt es ja verschiedene Ansätze für Probleme. Optimalisierungsprobleme finden hierbei die bestmögliche Lösung während Entscheidungsprobleme versuchen zu ermitteln, ob es eine Lösung für besagtes Probleme der Größe k gibt, wobei k zur Verfügung steht. Bei letzteren ist tatsächlich nur die Machbarkeit / Entscheidung also Ja oder Nein relevant.

Der Gedankengang, so wie ich es zumindest verstanden habe ist, dass es für ein in polynomialer Zeit lösbares Optimierungsproblem auch immer ein in polynomialer Zeit lösbares Entscheidungsproblem gibt*. Daher konzentriert sich die Komplexitätstheorie eher auf Entscheidungsprobleme, da diese nur 2 Outputs haben (0, 1).

Reduktion:
Ein problem X ist dann polynomiell* auf ein Problem Y reduzierbar, wenn es eine polynomiell zeitliche Funktion gibt, die den Eingangswert von X in einen Eingangswert von Y transformiert, so dass das Ergebnis von Y auch das Ergebnis für X ist.

Ein simples Beispiel für Reduktion wäre:

Y: Matrizenmultiplikation: M1 x M2 gibt dir eine neue Matrix mit den multiplizierten Elementen
X: Matrizenquadrierung: M^2

Dein Eingang für X wäre M, welcher durch eine polynomiell zeitliche Funktion in M1 und M2 zerlegt würde. M1 und M2 wären dann die Eingangsparameter für den Algorithmus von Y. Das Ergebnis von Y wäre sowohl das korrekte Ergebnis für X als auch für Y. Daher wäre X polynomiell auf Y reduzierbar.

Daraus resultiert: X ---poly--> Y
- ist Y polynomiell lösbar, ist auch X polynomiell lösbar
- Y ist mindestens genau so schwer zu lösen wie X

NPC und NP-Schwer:
Ein Problem Y in NPC kann man sich so global / allgemein vorstellen, dass man jedes Problem X in NP auf dieses Problem polynomiell reduzieren kann um dann mit Y, X lösen zu können.

Die Crux daraus ist dann, dass wenn man ein Problem Y in NPC finden würde, was in polynomieller Zeit lösbar wäre, dass dann wirklich alle anderen Probleme in P und NP auch in polynomieller Zeit lösbar wären.

Um jetzt zu zeigen, dass ein Problem in NPC liegt gibt es zwei Möglichkeiten:
1. Man beweist, dass das Problem Y in NP liegt und jedes andere Problem X in NP sich polynomiell darauf reduzieren lässt (sehr schwer)
2. Man zeigt, dass ein Problem X, das bereits in NPC liegt, sich auf das Problem Y reduzieren lässt (besser)

Bsp.: SAT (sehr aufwändig bewiesen von Cook & Levin) und CLIQUE sind z.B. beide in NPC, da man SAT polynomiell auf CLIQUE reduzieren kann. So kann man zeigen, dass ein "wahr" ergebender konjunktiver boolscher Term mit m Gliedern in einen Graphen umgeformt werden kann, der einen CLIQUE mit m Knoten hat (auch "wahr") und dass der gleiche Term in "unwahrer" Form keinen gültigen CLIQUE erzeugt (auch "unwahr"). Die Eingaben von SAT können also in Eingaben von CLIQUE umgewandelt und das Problem von SAT mit CLIQUE gelöst werden => SAT ---poly--->CLIQUE => CLIQUE ist in NPC.

Jetzt gab es noch die Frage nach NP-Schwer. Soweit ich das verstanden habe ist das die Konstellation, dass alle Probleme X in NP sich auf dieses Problem Y reduzieren lassen. Dabei muss aber Y nicht in NP sein. D.h. jedes Problem in NPC ist NP-Schwer aber nicht jedes NP-schwere Problem ist in NPC, da es dafür gewisse Kriterien gibt (z.B. Entscheidungsproblem, endliche Anzahl von Lösungen und jede Lösung in polynomialer Länge, usw.). Ein Beispiel für ein NP-schweres Problem das nicht in NPC liegt ist das Halteproblem von Turing.

Jetzt hoffe ich noch, dass das auch alles stimmt sonst ist mein ganzes Verständnis für die Klausur dahin.

Gruß
Marcus

*Korrektur von Herrn Weihe
Zuletzt geändert von nozyde am 24. Sep 2017 23:50, insgesamt 2-mal geändert.

Prof. Karsten Weihe
Dozentin/Dozent
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: NP-vollständig/NPC

Beitrag von Prof. Karsten Weihe » 24. Sep 2017 20:26

nozyde hat geschrieben:
24. Sep 2017 17:03
Entscheidungsprobleme:
Wenn man die Komplexität von Problemen betrachtet gibt es ja verschiedene Ansätze für Probleme. Optimalisierungsprobleme finden hierbei die bestmögliche Lösung während Entscheidungsprobleme versuchen zu ermitteln, ob es eine Lösung für besagtes Probleme der Größe k gibt, wobei k zur Verfügung steht. Bei letzteren ist tatsächlich nur die Machbarkeit / Entscheidung also Ja oder Nein relevant.
Die Größe k kommt dann vor, wenn aus einem Optimierungsproblem ein Entscheidungsproblem gebastelt wird (siehe Video/Foliensatz "Algorithmische Komplexität" in der Videothek Algorithmik auf youtube). Es gibt aber auch andere Entscheidungsprobleme, z.B. "können alle LVs im nächsten Semester passend in Hörsäle und Zeitslots gebucht werden".
nozyde hat geschrieben:
24. Sep 2017 17:03
Der Gedankengang, so wie ich es zumindest verstanden habe ist, dass es für ein in polynomialer Zeit lösbares Optimierungsproblem auch immer ein in polynomialer Zeit lösbares Entscheidungsproblem gibt und vice versa.
Nicht vice versa, siehe oben.
nozyde hat geschrieben:
24. Sep 2017 17:03
Daher konzentriert sich die Komplexitätstheorie eher auf Entscheidungsprobleme, da diese nur 2 Outputs haben (0, 1).
Ja, weil man sich sonst nicht nur mit der Transformation der Instanzen vom zu reduzierenden auf das reduzierte Problem, sondern auch noch mit der Rücktransformation der Lösung befassen müsste, was bei binären Lösungen trivial ist.
nozyde hat geschrieben:
24. Sep 2017 17:03
Reduktion:
Ein problem X ist auf ein Problem Y reduzierbar, wenn es eine polynomiell zeitliche Funktion gibt, die den Eingangswert von X in einen Eingangswert von Y transformiert, so dass das Ergebnis von Y auch das Ergebnis für X ist.
Dann ist X auf Y polynomiell reduzierbar.
nozyde hat geschrieben:
24. Sep 2017 17:03
Ein simples Beispiel für Reduktion wäre:
Y: Matrizenmultiplikation: M1 x M2 gibt dir eine neue Matrix mit den multiplizierten Elementen
X: Matrizenquadrierung: M^2
von Y transformiert, so dass das Ergebnis von Y auch das Ergebnis für X ist.
Ich stimme dem Beispiel zu.
nozyde hat geschrieben:
24. Sep 2017 17:03
- Y ist mindestens genau so schwer zu lösen wie X
Ja, konkreter: Die minimal mögliche asymptotische Komplexität von Y ist mindestens so hoch wie die von X.
nozyde hat geschrieben:
24. Sep 2017 17:03
NPC und NP-Schwer:
Ein Problem Y in NPC kann man sich so global / allgemein vorstellen, dass man jedes Problem X in NP auf dieses Problem polynomiell reduzieren kann um dann mit Y, X lösen zu können.
Stimme zu.
nozyde hat geschrieben:
24. Sep 2017 17:03
Die Crux daraus ist dann, dass wenn man ein Problem Y in NPC finden würde, was in polynomieller Zeit lösbar wäre, dass dann wirklich alle anderen Probleme in P und NP auch in polynomieller Zeit lösbar wären.
Stimme zu, wobei ich es nicht unbedingt eine Crux nennen würde.
nozyde hat geschrieben:
24. Sep 2017 17:03
Um jetzt zu zeigen, dass ein Problem in NPC liegt gibt es zwei Möglichkeiten:
1. Man beweist, dass das Problem Y in NP liegt und jedes andere Problem X in NP sich polynomiell darauf reduzieren lässt (sehr schwer)
2. Man zeigt, dass ein Problem X, das bereits in NPC liegt, sich auf das Problem Y reduzieren lässt (besser)
Stimme zu.
nozyde hat geschrieben:
24. Sep 2017 17:03
Jetzt gab es noch die Frage nach NP-Schwer.
Im Gegensatz zu NP-vollständig habeich zu NP-schwer schon verschiedene Definitionen gefunden. Ich verwende beides synonym, das ist auch die Verwendung in der Wikipedia (Artikel "NP-Schwere").

KW

nozyde
Erstie
Erstie
Beiträge: 20
Registriert: 7. Jun 2017 21:22

Re: NP-vollständig/NPC

Beitrag von nozyde » 24. Sep 2017 22:49

Vielen Dank Herr Weihe für die sehr ausführliche Antwort!

Antworten

Zurück zu „Archiv“