5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von Smith »

Hallo zusammen,

in der Aufgabenstellung heißt es:
"Zeigen Sie, dass jede der erfüllenden Belegungen einer k-Clique entspricht und umgekehrt, indem Sie das 3-CNF-Problem, gemäß der Vorlesung, auf das MAX-CLIQUE-Problem reduzieren".
Ist mit "gemäß der Vorlesung" gemeint, dass wir Beweise erarbeiten sollen? "Zeigen Sie" hört sich eher nach visualisieren an.
Ich möchte hier nur sicher gehen, dass meine Lösung definitiv als vollständig betrachtet wird.

Danke im Voraus!
Phil

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: 5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von Smith »

Um die Frage anders zu formulieren:

Wenn ich die MAX-CLIQUE gezeichnet habe und man anhand ihr ablesen kann, dass die erfüllenden Bedingungen jeweils eine k-Clique bilden (erfüllende Bedingunen wurden natürlich vorher gefunden und in der Zeichnung deutlich hervorgehoben) und ich andersherum für jede k-Clique, die aus der MAX-CLIQUE ablesbar ist, eine erfüllende Belegung auflisten kann, - ist die Aufgabe dann wunschgemäß erledigt?
Phil

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: 5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von R_Egert »

Wenn dazu der Algorithmus aus der Vorlesung verwendet wurde klingt das soweit gut :)

VIele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: 5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von Smith »

Danke für die Antwort, Rolf.

Ich weiß jedoch leider nicht genau was mit dem Algorithmus aus der Vorlesung gemeint ist.
Kann mich jemand zu den relevanten Lernmaterialien lotsen?
Bis jetzt habe ich mir für die Aufgabe das auf youtube hochgeladene VIdeo "Komplexität algorithmischer Probleme" und die entsprechenden Folien in den Vorlesungsmaterialien angeschaut (wie unter "wichtige Materialien" angegeben).
Hier gibt es die Abschnitte "Reduktion auf kürzeste Pfade" und "Reduktion von Problemen", jedoch erkenne ich hieraus keine genaue Vorschrift. In beiden gezeigten (illustrativen) Beispielen wird die Reduktion auf einen Graphen einfach neben das ursprüngliche Problem gestellt, ohne dass erklärt wird wie dabei vorgegangen wurde...

Beide Probleme in 5.1 werden schon in der Aufgabenstellung als NP-vollständig angegeben, also kann es ja eigentlich nicht um die Beweisfindung dafür gehen, dass die beiden Probleme aufeinander reduzierbar sind (das ist ja durch diese Angabe im Prinzip Voraussetzung - oder?...). Ist die eigentliche Reduktion des Problems nicht im Endeffekt einfach das Zeichnen des Graphen?

Ich denke nicht, dass die Aufgaben wirklich schwer zu lösen sind, aber überhaupt zu durchschauen was genau als Lösung erwartet wird, ist in diesem Testat meiner Meinung nach nur ziemlich vage formuliert und das absolut zeitaufwändigste an der ganzen Arbeit.

Ich habe für das Erarbeiten meiner Lösung keinen speziellen Algorithmus verwendet, sondern eine Wahrheitstabelle aufgestellt, den Graphen gezeichnet und in ihm die erfüllenden Bedingungen markiert, so dass ablesbar ist, dass jeder erfüllenden Bedingung eine 3-Clique entspricht. Dann habe ich alle 3-Cliquen aufgelistet und zu jeder dieser Cliquen auf eine entsprechende erfüllende Bedingung verwiesen, um zu zeigen, dass auch jeder 3-Clique eine erfüllende Bedingung entspricht.
Was genau fehlt an der Lösung bzw. wird zusätzlich erwartet? Muss ich irgend etwas beweisen?

Sorry für's Nachhaken, aber ich muss dieses Testat auf jeden Fall bestehen und bin mir sehr unsicher was genau von mir erwartet wird.

Viele Grüße und danke schon mal!

ek65baze
Windoof-User
Windoof-User
Beiträge: 29
Registriert: 24. Apr 2015 18:46

Re: 5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von ek65baze »

Ich kann smith hier nur zustimmen, die Aufgabenstellung ist mir ebenfalls etwas ungenau, sowie kann ich keine direkte Vorgehensweise aus den Folien oder dem OWL Video herausinterpretieren.

R_Egert
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 180
Registriert: 8. Sep 2009 23:27

Re: 5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von R_Egert »

Smith hat geschrieben: Beide Probleme in 5.1 werden schon in der Aufgabenstellung als NP-vollständig angegeben, also kann es ja eigentlich nicht um die Beweisfindung dafür gehen, dass die beiden Probleme aufeinander reduzierbar sind (das ist ja durch diese Angabe im Prinzip Voraussetzung - oder?...). Ist die eigentliche Reduktion des Problems nicht im Endeffekt einfach das Zeichnen des Graphen?
Jep, Aufgabe 1 wurde ja bereits in der VL behandelt und dient in diesem Falle eher der Einarbeitung in das Thema, bzw. der Verständnisförderung des Reduktionsverfahrens. :twisted:
Smith hat geschrieben: Ich denke nicht, dass die Aufgaben wirklich schwer zu lösen sind, aber überhaupt zu durchschauen was genau als Lösung erwartet wird, ist in diesem Testat meiner Meinung nach nur ziemlich vage formuliert und das absolut zeitaufwändigste an der ganzen Arbeit.
Naja, das ist ja gerade die Schwierigkeit an Reduktionen, nämlich das eigentliche Finden dieser Reduktionen. Da die Übung vorraussetzt, dass man sich irgendwie mit der VL beschäftig hat (Oder das zum bearbeiten der Übung nun tut :)) wäre die einzige Möglichkeit die Aufgabe 1 exakter zu formulieren, den Lösungsweg anzugeben. Anstelle dessen sind die Folien gelistet, auf denen man sich diesen "anlesen" kann. Hinweise: Hierbei handelt es sich nicht um konkrete durchzuführende Schritte, sondern um einzuhaltenden Bedinungen. ;)
Smith hat geschrieben: Ich habe für das Erarbeiten meiner Lösung keinen speziellen Algorithmus verwendet, sondern eine Wahrheitstabelle aufgestellt, den Graphen gezeichnet...

Wie wurde denn der Graph gezeichnet? ;) Ein Algorithmus beschreibt nur eine strukturierte Vorgehenseweise, welche dabei wohl vorhanden war :twisted:
Smith hat geschrieben: und in ihm die erfüllenden Bedingungen markiert, so dass ablesbar ist, dass jeder erfüllenden Bedingung eine 3-Clique entspricht. Dann habe ich alle 3-Cliquen aufgelistet und zu jeder dieser Cliquen auf eine entsprechende erfüllende Bedingung verwiesen, um zu zeigen, dass auch jeder 3-Clique eine erfüllende Bedingung entspricht.
Was genau fehlt an der Lösung bzw. wird zusätzlich erwartet? Muss ich irgend etwas beweisen?

Das klingt doch soweit gut! Somit sollte alles für die Aufgabe relevante Bewiesen sein, interessant wäre vielleicht noch ob die k-cliquen eindeutig sind, oder ob aus einer Belegung meherere resultieren können?

Viele Grüße,

Rolf
Tutor:
  • Einführung in Trusted Systems WS11/12, WS12/13, WS13/14, WS14/15
  • GDI II SS11, SS12, SS13, SS14
  • Einführung in die Kryptographie WS14/15

Smith
Mausschubser
Mausschubser
Beiträge: 53
Registriert: 13. Apr 2015 15:45

Re: 5.1 3-CNF-Problem auf MAX-CLIQUE reduzieren

Beitrag von Smith »

Damit hast du mir denke ich alle Fragen beantwortet. Ich formuliere nun noch mein Vorgehen in Anlehnung an die Folien und schließe die Aufgabe dann damit ab.

Vielen Dank für das ausführliche Eingehen auf meine Unsicherheiten : )
Phil

Antworten

Zurück zu „Archiv“