Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Beitrag von sqrt(2) » 13. Sep 2016 12:54

Hallo,

hier sind mir erneut eine Reihe von Fragen aufgekommen. Zitate sind aus dem Drehbuch Komplexität algorithmischer Probleme.pdf

Frage 1: Der Ausgangspin des letzten Gatters ist der Ausgangspin des ganzen Schaltkreises.
Warum?
Wir betrachten ja für jeden Gatter das dazugehörige Ausgangspin und warum ist der Ausgangspin vom letzten Gatter unser Ausgangspin des ganzen Schaltkreises? Und warum werden die Gatter immer schmaler in Richtung des Ausgangs (vgl. Folie 38 bzw. Frage 4)?

Frage 2: Wir gehen nicht von einem bestimmten Computer aus und wissen daher nicht, wie groß er als Schaltnetz ist und wie groß das Teilnetz ist, das tatsächlich für den Durchlauf des Algorithmus verwendet wird
Da X aus NP ist gibt es ein Zertifikat und ein Prüfalgorithmus und daher wird aus dem ganzen Computerschaltnetz nur ein Teilnetz betrachtet, oder? (Meine ja...) Aber warum muss das Teilnetz dann nich polynomiell groß sein? Und warum gibt es für dieses Teilnetz ein äquivalentes Schaltnetz das nur polynomiell groß ist? Liegt es daran das (wie im Video gesagt) jede logische Formal sich durch polynomiell große Anzahl von log. Gattern darstellen lässt? (Meine ja...) ABER ich verstehe dann nicht ganz warum das Teilnetz nicht polynomiell groß ist, wenn man es polynomiell transformieren kann...

Frage 3: Eine wichtige Modifikation im Design des Schaltnetzes: (...) diejenigen Eingabespins, die den Input selbst kodieren, fest verdrahtet sind.
Ich verstehe nicht ganz wo das Problem ist wenn es nicht fest verdrahtet ist. Doof gefragt "kann man nicht einfach etwas aufpassen, das man die Eingangspins gemäß des Zertifikats anlegt?"

Frage 4: Schematische Darstellung des Schaltkreises
Warum ist der Schaltkreis dreieckig?
Wiese ist "für den Input" und "für das Zertifikat" schwarz hinterlegt?

Frage 5: Durch diese Äquivalenz zwischen (...) also NP-Vollständig (erster Absatz S.19)
X ist aus NP, also ex. Prüfalg und Zertifikat. Wir können X polynomiell reduzieren (da sich jede logische Formel durch polynomiell große Anzahl von logischen Gattern darstellen lässt {da X von einem Computer gelöst wird ist X eine riesige logische Formel aus 0 und 1?]). Jetzt "werfen" wir X in unseren Schaltkreis und erhalten als Ausgangspin eine 1 oder 0. Erhalten wir eine 1 ist X ein zertifizierter Ja-Input. Da wir ja jetzt eine 1 Output haben sagen wir, das es sich bei X um einen zertifizierten Ja Input handelt. Weil der Zufall es so will ist nun der Input in denjenigen Eingangspins kodiert, die nun einmal den Input kodieren sollen. Und irgendwelche Signale liegen an den Eingangspins, die das Zertifikat kodieren sollen Mhm okay... Dann heißt es aber das man mit ein bisschen Glück beim ersten Versuch X richtig kodiert haben kann und falls nicht, dann probiert man es einfach nochmal, denn irgendwann wird schon 1 als Ausgangspin rauskommen

Frage 6: Circuit SAT auf SAT
Das ist ja eig. trivial. Aber was ist mit (Folie 40:) "es eine Belegung der booleschen Variablen gibt" gemeint? Wie soll ich mir das am besten vorstellen? Das mit dem Schaltkreis und den Gattern war anschaulich. Ist das hier einfach formal gemeint?

Frage 7: 3-CNF
Was ist die Motivation SAT einzuschränken um zu zeigen das 3CNF auch NPC ist?

Frage 8: Widerspruch? Zitate aus dem Drehbuch: Dass SAT NP-schwer ist, heißt aber noch lange nicht, dass auch eine solche Einschränkung NP-schwer ist. VS Wenn ein Problem wie SAT in NP ist, muss natürlich auch jede Einschränkung wie 3-CNF in NP sein (s.20)

Frage 9: Konjunktive Normalorm
https://de.wikipedia.org/wiki/Konjunktive_Normalform
Warum setzen wir X auf nein, wenn eines der ersten beiden Literale wahr ist? Dann können wir doch X genau so gut auf wahr setzen? (Zwar ist in der anderen Klausel x negiert aber wenn in der Klausel K' mind. 1 Literal wahr ist dann wäre es ja auch okay wenn x nein ist)

Frage 10: Äquivalenzumformumg
Ich verstehe nicht ganz. Wir sagen um zu argumentieren, das es sich um eine Äquivalenzumformung handelt
Variante A: (Betrachten wir zuerst eine Belegung (...) K' und K'' erfüllt.) funktioniert
Variante B: Wir überführen K in CNF sodass K nicht erfüllt ist (sprich wir machen einen Fehler) dann können wir x beliebig setzen, am Ende haben wir trotzdem ein falsches Ergebnis und daher muss es eine Äquivalenzumformung sein? (Verstehe ich nicht... [Habe auch keine Formale Grundlagen als Modul])
Weil wir eine Äquivalenzumformung haben haben wir gezeigt das 3CNF in NPC ist? (Meine ja...) (wie gesagt die Äquivalenzumformung habe ich nicht verstanden bzw. die Argumentation)

Frage 11: Verallgemeinerung von 3 CNF NP Vollständig
Das ist für mich nicht intuitiv, weil das allgemeinere muss ja nicht der Regel des spezifischen unterliegen...
Wir sind ja eig. auch den anderen Weg gegangen

Frage 12: Ausnahme: Wenn zwei Literale aus verschiedenen Klauseln dieselbe Boolesche Variable sind, aber einmal negiert und einmal unnegiert, dann sind die beiden zughörigen Knoten nicht durch eine Knate verbunden
Wie ist das motiviert? Ich hätte bspw. gesagt zwei Literale die gleich sind (unnegiert und unnegiert) sollen nicht mit einer Kante verbunden sein (warum ist das unintuitiv oder falsch?)
Es wäre sehr Hilfreich, wenn Sie in Ihrer Argumentation die Absätze (s.23) 1. Zuerst nehmen wir an ... Klauseln erfüllt. 2. Umgekehrt nehmen ... gerade k. einbauen weil ich glaube das ist die Antwort auf meine Frage nur verstehe ich die Antwort nicht...

Fragen zu 1.
- Warum kann keine Variable auf wahr und falsch zugleich gesetzt werden, wenn keine Kante zw. einer negierten und einer nunnegierten Variable existiert? (Ich nehme an die Konsistenz ergibt sich daraus...?)
Zuletzt geändert von sqrt(2) am 15. Sep 2016 17:03, insgesamt 2-mal geändert.

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Beitrag von sqrt(2) » 14. Sep 2016 09:50

Falls die Fragen zu unpräzise sind oder was nicht klar sein sollte, würde ich mich über ein Feedback freuen. Dann würde ich die Fragen umformulieren. Aber eine Antwort wäre mir sehr wichtig (:

Sonne34
Windoof-User
Windoof-User
Beiträge: 26
Registriert: 3. Mai 2015 18:10

Re: Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Beitrag von Sonne34 » 14. Sep 2016 10:51

sqrt(2) hat geschrieben:Hallo,

hier sind mir erneut eine Reihe von Fragen aufgekommen. Zitate sind aus dem Drehbuch Komplexität algorithmischer Probleme.pdf
Hallo, kannst du mir bitte sagen, wo du das Drehbuch gefunden hast? Ich finde es leider nicht :(

Liebe Grüße

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Beitrag von sqrt(2) » 14. Sep 2016 11:01

Sonne34 hat geschrieben: Hallo, kannst du mir bitte sagen, wo du das Drehbuch gefunden hast? Ich finde es leider nicht :(
Wenn man sich die ganzen Vorlesungsmaterialien runter lädt, dann ist dies bei mir im Ordner ComplexityOfProblems. Hab's dir mal angehängt.
Dateianhänge
Drehbuch Komplexität algorithmischer Probleme.pdf
(167.73 KiB) 50-mal heruntergeladen

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

Re: Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Beitrag von Prof. Karsten Weihe » 14. Sep 2016 20:45

sqrt(2) hat geschrieben: Frage 1: Der Ausgangspin des letzten Gatters ist der Ausgangspin des ganzen Schaltkreises.
Warum?
Wir betrachten ja für jeden Gatter das dazugehörige Ausgangspin und warum ist der Ausgangspin vom letzten Gatter unser Ausgangspin des ganzen Schaltkreises?
Ich bin mir nicht sicher, ob ich Ihre Frage richtig verstehe. Der betrachtete Zertifizierungsalgorithmus hat ja nur ein Bit ja/nein als Ausgabe. Wenn man einen Algorithmus als Schaltkreis kodiert, dann kommt halt ein Schaltkreis mit so vielen Ausgabepins heraus, wie dieser Algorithmus an Bits zurückliefert..
sqrt(2) hat geschrieben: Und warum werden die Gatter immer schmaler in Richtung des Ausgangs (vgl. Folie 38 bzw. Frage 4)?
Darstellerische Freiheit des Dozenten. :wink:
sqrt(2) hat geschrieben: Frage 2: Wir gehen nicht von einem bestimmten Computer aus und wissen daher nicht, wie groß er als Schaltnetz ist und wie groß das Teilnetz ist, das tatsächlich für den Durchlauf des Algorithmus verwendet wird
Da X aus NP ist gibt es ein Zertifikat und ein Prüfalgorithmus und daher wird aus dem ganzen Computerschaltnetz nur ein Teilnetz betrachtet, oder? (Meine ja...) Aber warum muss das Teilnetz dann nich polynomiell groß sein? Und warum gibt es für dieses Teilnetz ein äquivalentes Schaltnetz das nur polynomiell groß ist?
Damit wollte ich letztendlich nur sagen: Ohne Beschränkung der Allgemeinheit können wir davon ausgehen, dass das Teilnetz polynomiell groß ist.
sqrt(2) hat geschrieben: Frage 3: Eine wichtige Modifikation im Design des Schaltnetzes: (...) diejenigen Eingabespins, die den Input selbst kodieren, fest verdrahtet sind.
Ich verstehe nicht ganz wo das Problem ist wenn es nicht fest verdrahtet ist. Doof gefragt "kann man nicht einfach etwas aufpassen, das man die Eingangspins gemäß des Zertifikats anlegt?"
Ich denke, man kann es auch so sagen wie Sie.
sqrt(2) hat geschrieben: Frage 4: Schematische Darstellung des Schaltkreises
Warum ist der Schaltkreis dreieckig?
Siehe oben, darstellerische Freiheit. Ich hätte dem Schaltkreis auch die Form der Gemarkung Darmstadt oder den Schattenriss von Darth Vader als Umrissform geben können, aber ob das verständlicher gewesen wäre...
sqrt(2) hat geschrieben: Wiese ist "für den Input" und "für das Zertifikat" schwarz hinterlegt?
Was ist das Problem?
sqrt(2) hat geschrieben: Jetzt "werfen" wir X in unseren Schaltkreis und erhalten als Ausgangspin eine 1 oder 0.
???
sqrt(2) hat geschrieben: Frage 6: Circuit SAT auf SAT
Das ist ja eig. trivial. Aber was ist mit (Folie 40:) "es eine Belegung der booleschen Variablen gibt" gemeint? Wie soll ich mir das am besten vorstellen? Das mit dem Schaltkreis und den Gattern war anschaulich. Ist das hier einfach formal gemeint?
Sie wissen, was eine "Belegung einer Variable" ist, nämlich die Zuweisung eines Wertes an diese Variable?
sqrt(2) hat geschrieben: Frage 7: 3-CNF
Was ist die Motivation SAT einzuschränken um zu zeigen das 3CNF auch NPC ist?
Man kann 3-CNF auf Probleme polymomiell reduzieren, auf die man SAT nicht direkt reduzieren kann (zumindest weiß niemand wie).
sqrt(2) hat geschrieben: Frage 8: Widerspruch? Zitate aus dem Drehbuch: Dass SAT NP-schwer ist, heißt aber noch lange nicht, dass auch eine solche Einschränkung NP-schwer ist. VS Wenn ein Problem wie SAT in NP ist, muss natürlich auch jede Einschränkung wie 3-CNF in NP sein (s.20)
Ich finde hier keinen Widerspruch. Worin soll der Widerspruch bestehen?
sqrt(2) hat geschrieben: Frage 9: Konjunktive Normalorm
Warum setzen wir X auf nein, wenn eines der ersten beiden Literale wahr ist? Dann können wir doch X genau so gut auf wahr setzen? (Zwar ist in der anderen Klausel x negiert aber wenn in der Klausel K' mind. 1 Literal wahr ist dann wäre es ja auch okay wenn x nein ist)
Kann sein ... was würde daraus folgen?
sqrt(2) hat geschrieben: Frage 10: Äquivalenzumformumg
Weil wir eine Äquivalenzumformung haben haben wir gezeigt das 3CNF in NPC ist?
Ja, denn Reduktion X -> Y heißt ja, dass die gegebene Instanz von X und die Instanz von Y, auf die erstere reduziert wird, äquivalent sind. Bei Entscheidungsproblemen X und Y heißt das einfach: Die eine Instanz ist eine Ja-Instanz genau dann, wenn die andere Instanz eine Ja-Instanz ist.
sqrt(2) hat geschrieben: Frage 11: Verallgemeinerung von 3 CNF NP Vollständig
Das ist für mich nicht intuitiv, weil das allgemeinere muss ja nicht der Regel des spezifischen unterliegen...
Wenn ein Problem X in NPC und eine Verallgemeinerung Y von X in NP ist, dann ist auch Y in NPC (Beweis durch triviale Reduktion von X auf Y, wo jede Instanz von X auf sich selbst reduziert wird).
sqrt(2) hat geschrieben: Frage 12: Ausnahme: Wenn zwei Literale aus verschiedenen Klauseln dieselbe Boolesche Variable sind, aber einmal negiert und einmal unnegiert, dann sind die beiden zughörigen Knoten nicht durch eine Knate verbunden
Wie ist das motiviert?
Die Idee ist doch, dass eine Clique maximaler Größe im Graphen gerade einem Literal pro Klausel entspricht, so dass die gewählten Literale alle wahr sind, also die ganze Formel wahr ist. Das ist aber genau dann in sich widersprüchlich, wenn in der Clique eine Variable einmal negiert und einmal unnegiert vorkommt, denn dann müsste diese Variable zugleich wahr und falsch sein.
sqrt(2) hat geschrieben: Fragen zu 1.
- Warum kann keine Variable auf wahr und falsch zugleich gesetzt werden, wenn keine Kante zw. einer negierten und einer nunnegierten Variable existiert? (Ich nehme an die Konsistenz ergibt sich daraus...?)
Umgekehrt: Da keine solche Kante existiert, können wir die Variablen in einer Clique so setzen, dass alle diese Literale zugleich wahr sind (also die Formel insgesamt wahr ist).

Puuuh, soweit für's erste ... (ich nehme an, Sie haben Anschlussfragen?)

KW

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 202
Registriert: 12. Apr 2015 11:35

Re: Komplexität algorithmischer Probleme: Problemstellung die in NPC sind

Beitrag von sqrt(2) » 15. Sep 2016 21:28

Prof. Karsten Weihe hat geschrieben: Puuuh, soweit für's erste ... (ich nehme an, Sie haben Anschlussfragen?)
Nein zunächst nicht. Vielen Dank Herr Weihe!
Nichts desto trotz, fühle ich mich irgendwie nicht so wirklich gut vorbereitet für die Theoriefragen...

Antworten

Zurück zu „Archiv“