Fachrat Informatik - Forum

Das ist doch trotzdem genau mein Vorgehen oder nicht? Nur dass ich fälschlicherweise argumentiert habe, dass wir schon einen HAMCIRC wissen und nicht gesagt habe, dass durch dieses Vorgehen ein HAMCIRC zum EVEN-HAMCIRC wird und ein nicht-vorhandener HAMCIRC auf keinen Fall zu einem gemacht wird.

[EDIT: Hm, muss noch mal etwas genauer drüber nachdenken.]

Quoted from "Arne"

Versuche zu zeigen, dass gilt. Hinweis: Du musst hierzu und zeigen.

Muß man das tatsächlich in dieser Ausführlichkeit zeigen? Ich hätte in der Klausur wahrscheinlich geschrieben "Das sieht man".



Andere Basis bzw. anderer Logarithmus ändert das ganze nur um einen konstanten Faktor, der bei der O-Notation dann sowieso wegfällt.

Zu HAMCIRC und EVEN-HAMCIRC bin ich ehrlich gesagt ein bisschen ratlos. Mir fällt nichts mehr ein.

Deswegen noch eine Frage zu Blatt 6, Aufgabe 2. Hier soll gezeigt werden, dass DOUBLE-SAT := {< | ist eine aussagenlogische Formel, die mind. zwei erfüllende Belegungen besitzt} NP-vollständig ist.

Ich würde von SAT aus reduzieren. Wenn ein SAT ist, hat es ja eine erfüllende Belegung. Meine Reduzierungsfunktion würde nun jede Wahrheitsvariable in für sich genommen negieren (also alle Verknüpfungen unangetastet lassen, kein DeMorgan o.ä.). Damit ist immer noch erfüllt, falls es eine erfüllende Belegung war, somit ist eine zweite erfüllende Belegung gefunden, aber es ist auch nicht erfüllt, falls es das vorher nicht war.
Dies läuft offensichtlich in polynomieller Zeit ab, da ja lediglich für jede vorhandene Variable ein Mal negiert wird.

Und gleich noch eine, Blatt 7, A1 mit INDEPENDENT SET := {<G, k> | G hat eine unabhängige Knotenmenge mit k Knoten }.

Reduktion von CLIQUE.
Eingabe ist <G, k> CLIQUE, also ein Graph, der eine CLIQUE der Größe k enthält. Meine Funktion f erstellt einen Graphen G' mit einer CLIQUE der Größe k und hängt zusätzlich an jeden dieser Knoten einen weiteren Knoten an. Somit haben wir k zusätzliche Knoten, die untereinander unabhängig sind, also ist G' INDEPENDENT SET gdw. G CLIQUE. Wenn G nicht in CLIQUE war, kann natürlich auch kein neuer Graph mit einer CLIQUE der Größe k erstellt werden.

Sorry dass ich hier so mit Fragen um mich werfe.

Quoted from "Skuld"

Zu HAMCIRC und EVEN-HAMCIRC bin ich ehrlich gesagt ein bisschen ratlos. Mir fällt nichts mehr ein.

Überlege mal, ob Deine letzte Idee vielleicht funktioniert, wenn man das für jede Kante in G macht. Falls ja, begründe warum.

Quoted from "Skuld"

Deswegen noch eine Frage zu Blatt 6, Aufgabe 2. Hier soll gezeigt werden, dass DOUBLE-SAT := {< | ist eine aussagenlogische Formel, die mind. zwei erfüllende Belegungen besitzt} NP-vollständig ist.

Ich würde von SAT aus reduzieren. Wenn ein SAT ist, hat es ja eine erfüllende Belegung. Meine Reduzierungsfunktion würde nun jede Wahrheitsvariable in für sich genommen negieren (also alle Verknüpfungen unangetastet lassen, kein DeMorgan o.ä.). Damit ist immer noch erfüllt, falls es eine erfüllende Belegung war, somit ist eine zweite erfüllende Belegung gefunden, aber es ist auch nicht erfüllt, falls es das vorher nicht war.
Dies läuft offensichtlich in polynomieller Zeit ab, da ja lediglich für jede vorhandene Variable ein Mal negiert wird.

Warum sollte die neue Formel denn mind. zwei erfüllende Belegungen haben? Ich denke nicht, dass das funktioniert. Beispielsweise wenn . Dann ist klar erfüllbar, aber Deine daraus entstandene Formel besitzt immer nur noch eine erfüllende Belegung und ist damit *nicht* in Double-SAT.

Quoted from "Skuld"

Zu HAMCIRC und EVEN-HAMCIRC bin ich ehrlich gesagt ein bisschen ratlos. Mir fällt nichts mehr ein.

In den Übungsaufgaben haben wir übrigens nicht HAMCIRC sondern HAMPATH für die Reduktion verwendet (Eingabe <G, s, t> mit s,t Start- bzw. Endknoten des Pfads) ...

Ah okay, wenn man das für jede Kante macht, wird durch die Verdopplung auf jeden Fall eine gerade Zahl erzeugt.

Quoted from "Arne"

Warum sollte die neue Formel denn mind. zwei erfüllende Belegungen haben? Ich denke nicht, dass das funktioniert. Beispielsweise wenn . Dann ist klar erfüllbar, aber Deine daraus entstandene Formel besitzt immer nur noch eine erfüllende Belegung und ist damit *nicht* in Double-SAT.

Argh, immer diese Grenzfälle. Dann würde ich sagen, hängt man an das ein "v x" ran (also ein "oder" x), wobei x eine nicht in vorkommende Variable. Wie diese belegt ist, ändert nichts an der (Nicht-)Erfüllbarkeit, ist die Formel aber erfüllbar, gibt es noch eine weitere erfüllende Belegung?

Hm, also was ich aus dieser Diskussion lerne: Algorithmen auf keinen Fall zu mathematisch/detailreich, sondern einfach schriftlich aufschreiben wie Skuld es gemacht hat...

Es ist viel einfacher zu schreiben: e := erste Kante des hamiltonschen Kreises in E statt zu versuchen das irgendwie zu "mathematisieren".

Quoted from "Skuld"

Argh, immer diese Grenzfälle. Dann würde ich sagen, hängt man an das ein "v x" ran (also ein "oder" x), wobei x eine nicht in vorkommende Variable. Wie diese belegt ist, ändert nichts an der (Nicht-)Erfüllbarkeit, ist die Formel aber erfüllbar, gibt es noch eine weitere erfüllende Belegung?

Nunja, wenn unerfüllbar ist und mindestens eine Variable -- sagen wir mal y -- enthält, dann besitzt doch wohl auch mindestens zwei erfüllende Belegungen! Nämlich x=1, y=0 und x=1, y=1.

Quoted from "Xular"

Es ist viel einfacher zu schreiben: e := erste Kante des hamiltonschen Kreises in E statt zu versuchen das irgendwie zu "mathematisieren"

Hiermit stimme ich nicht überein. Insbesondere eine solche Aussage wirft die Frage auf, wie man die erste Kante des hamiltonschen Kreises bestimmen will, wenn man den hamiltonschen Kreis nach unserem Wissen nur in NP bestimmen kann. Das ganze dann innerhalb einer Polynomialzeit Many-One Reduktion zu verwenden ist also eher fatal.

Edit: Insbesondere das Mathematisieren ist daher sinnvoll, als dass man die Sache sehr viel intensiver durchdenkt und vorallem damit versucht zu konkretisieren. Wenn man es einfach schriftlich aufschreibt, dann hat man es anscheinend nicht wirklich geprüft und vermutet nur, dass es funktioniert. Eben genauso wie wir hier im Thread schon einige andere Versuche gesehen haben, die im Endeffekt keine Lösungen sind, sondern nur Fragen der Form "Geht's vielleicht jetzt so? Ich bin zu faul genauer drüber nachzudenken.".

Wenn ich mir allerdings einige 'Musterlösungen', die in den Übungen an die Tafel gebracht wurden anschaue, dann sieht das ähnlich aus...
Beispielsweise die Frage, ob LPATH in NP liegt:
Zertifikat: Knotenmenge oder Pfad P
Eingabe: <G,u,v,k>
Prüfe, ob Eingabe korrekt und der Pfad P die Länge mindestens k hat, einfach ist und ein Pfad u zu v ist. Diese Prüfung geht in O(|V| + |V|²). => polynomiell => LPATH liegt in NP

Mag sein, dass da gerade nur noch wenig Zeit war aber das würde in der Klausur wohl kaum reichen...?

Quoted from "Xular"

Wenn ich mir allerdings einige 'Musterlösungen', die in den Übungen an die Tafel gebracht wurden anschaue, dann sieht das ähnlich aus...
Beispielsweise die Frage, ob LPATH in NP liegt:
Zertifikat: Knotenmenge oder Pfad P
Eingabe: <G,u,v,k>
Prüfe, ob Eingabe korrekt und der Pfad P die Länge mindestens k hat, einfach ist und ein Pfad u zu v ist. Diese Prüfung geht in O(|V| + |V|²). => polynomiell => LPATH liegt in NP

Mag sein, dass da gerade nur noch wenig Zeit war aber das würde in der Klausur wohl kaum reichen...?

Also genau genommen ist ja die Eingabe von dem P-Verifikationsalgorithmus <G,u,v,k> *und* der Pfad P (in dem Zusammenhang ist mir zudem gerade nicht klar, was mit Knotenmenge gemeint ist). Der Algorithmus an sich ist im Endeffekt schon so kurz. Das einzige was da vielleicht noch fehlt ist, dass man nur "wahr" zurück gibt, wenn die Prüfung keine Verletzungen der dort geprüften Eigenschaft hervorgebracht hat. Zur Laufzeitabschätzung hätte ich wohl noch ein wenig ausführlicher begründet, woher die Terme da kommen. Also |V| wegen durchlaufen des Pfades und prüfen ob jede Kante auch im Graphen dann vorhanden ist, sowie |V|² da man für jeden Knoten im Pfad prüfen muss, ob er nochmal auftaucht (Widerspruch zur Einfachheit).

Quoted from "cartman"

auch wenn es mit dem Nachdenken wahrscheinlich an mich gerichtet war, versuche ich jetzt die übrigen Aufgaben zu den Klassenbeziehungen auch noch

Aufgabe: NL (echte Teilmenge von) PSPACE

NL=NSPACE(log n) (Teilmenge von) SPACE((log n)²)

PSPACE=(Vereinigung von) SPACE(n^k)

=>

SPACE((log n)²) (echte Teilmenge von) SPACE(n^k) /wobei man für das n^k
jetzt noch zeigen müsste, dass es echt schnell wächst als (log n)², also
z.B. f.a. k : n^k (Element von) O(n*log n)

dann sollte der Hierarchiesatz gelten

Gute Idee, den "f.a. k"-Teil kann man abkürzen:


: Satz von Savitch
: Platzhierarchiesatz, da

Kleiner Edit: das zweite da, muss man natürlich noch mit der Grenzwertabschätzung beweisen..

Okay, dann noch eine Frage zu Aufgabe 2 der ss10 Klausur, zu der es ja eine Musterlösung gab.

Dort wird das Optimierungsproblem sehr mathematisch beschrieben, allerdings wurden in den Übungen die Optimierungsprobleme meistens mit einfachem Text beschrieben.

Nehmen wir mal an ich hätte die Klausur mitgeschrieben und dort folgendes geantwortet:

I: Tupel aus Versandkosten pro Shop mit den jeweiligen Buchpreisen des Shops
Sol: Jede mögliche Kombination aus Versandkosten und Buchpreis
m: Gesamtkosten der Bücher (Versandkosten + Buchpreis des jeweiligen Shops)
goal: min

Wäre das auch eine akzeptabele Lösung?


Danke für die ausführliche Hilfe bisher, Arne

Quoted from "Xular"

Okay, dann noch eine Frage zu Aufgabe 2 der ss10 Klausur, zu der es ja eine Musterlösung gab.

Dort wird das Optimierungsproblem sehr mathematisch beschrieben, allerdings wurden in den Übungen die Optimierungsprobleme meistens mit einfachem Text beschrieben.

Nehmen wir mal an ich hätte die Klausur mitgeschrieben und dort folgendes geantwortet:

I: Tupel aus Versandkosten pro Shop mit den jeweiligen Buchpreisen des Shops
Sol: Jede mögliche Kombination aus Versandkosten und Buchpreis
m: Gesamtkosten der Bücher (Versandkosten + Buchpreis des jeweiligen Shops)
goal: min

Wäre das auch eine akzeptabele Lösung?


Danke für die ausführliche Hilfe bisher, Arne

Bei Sol hätte ich jetzt eher gesagt, dass hier Zuordnungen der Bücher zu den Shops gesucht ist. Sprich wo ich was kaufe. Ansonsten stimmt es vom textuellen Standpunkt her
Dennoch sollte man hier für eine volle Punktzahl eine formalisierte Lösung hinkriegen. Wenn Du erst das so umgangssprachlich aufschreibst, da Du nicht so sicher in der formalen Aufschreibweise bist, kann man da dann noch mehr Teilpunkte erhaschen, als wenn man es nur formal, aber falsch aufschreibt.

Dann noch eine Frage von mir ...

Übungsblatt 10, Aufg. 1 (wurde bei uns in der Übung anscheinend nicht gerechnet, zumindest finde ich in meinem Mitschrieb nichts ...)

zeige NP-Vollständigkeit:
UHAMPATH := { <G, s, t> | G ist ungerichteter Graph, der einen Hamiltonschen Pfad von s nach t besitzt }

In der Vorlesung hatte wir ja HAMPATH (für gerichtete Graphen), so daß die Reduktion ja höchstwahrscheinlich von HAMPATH ausgeht:

HAMPATH UHAMPATH

Im Prinzip ist klar, was zu tun ist: Man muß eine Funktion finden, die einen gerichteten in einen ungerichteten Graphen überführt, so daß ein evtl. vorhandener Hamilton-Pfad erhalten bleibt, aber kein Hamilton-Pfad erzeugt wird.

Nur: ich habe absolut keine Idee wie diese Funktion aussehen soll (und vor demselben Problem stehe ich bei ca. 90% der anderen "Zeige NP-Vollständigkeit"-Aufgaben . Bei fast allen Übungsaufgaben dasselbe: "Aha, so macht man das also , aber wie zum Kuckuck soll man da drauf kommen...?)

Quoted from "Panoramix"

Dann noch eine Frage von mir ...
Nur: ich habe absolut keine Idee wie diese Funktion aussehen soll (und vor demselben Problem stehe ich bei ca. 90% der anderen "Zeige NP-Vollständigkeit"-Aufgaben . Bei fast allen Übungsaufgaben dasselbe: "Aha, so macht man das also , aber wie zum Kuckuck soll man da drauf kommen...?)

Tjo, geht mir auch so. Ich denke deswegen fliegen auch immer soviele durch bei den KVA Klausuren...
Und diesesmal wird uns vermutlich nicht Aufgabe 1 "geschenkt", so wie bei der SS10 Klausur :/ (Wäre sonst das dritte mal *g*)

Was enorm helfen würde wäre der Ausschluss einiger Probleme, sodass man nicht bei allen vorgestellten Problemen genau wissen muss, wie sie funktionieren, um dann evtl darauf reduzieren zu können - das wurden ja in den letzten Jahren immer mehr Probleme, finde sehr viele in den Übungen behandelte Probs in alten Klausuren wieder...

Quoted from "Xular"

das wurden ja in den letzten Jahren immer mehr Probleme, finde sehr viele in den Übungen behandelte Probs in alten Klausuren wieder...

Naja, es waren erst Klausuraufgaben, die dann als Übungsaufgaben wiederverwendet wurden ...

Ich kann mich dunkel daran erinnern, daß im Tutorium vor der letzten Klausur gesagt wurde, daß man davon ausgehen könne, daß man von einem NP-Problem aus der Vorlesung ausgehend reduzieren könne. Ob diese Aussage auch für die aktuelle Klausur gilt, kann ich natürlich nicht sagen ...

Quoted from "Panoramix"

Dann noch eine Frage von mir ...

Übungsblatt 10, Aufg. 1 (wurde bei uns in der Übung anscheinend nicht gerechnet, zumindest finde ich in meinem Mitschrieb nichts ...)

zeige NP-Vollständigkeit:
UHAMPATH := { <G, s, t> | G ist ungerichteter Graph, der einen Hamiltonschen Pfad von s nach t besitzt }

In der Vorlesung hatte wir ja HAMPATH (für gerichtete Graphen), so daß die Reduktion ja höchstwahrscheinlich von HAMPATH ausgeht:

HAMPATH UHAMPATH

Also ich habe mir dazu folgendes aufgeschrieben aus der Übung:

Wir konstruieren einen neuen Graphen G' = (V', E'), mit:

V' = { | v V} (für jeden Knoten in V 3 neue Knoten erstellen)
E' = { | v V} { | v V} { | (u, v) E }

Nun gilt:
<G, s, t> HAMPATH => es existiert ein Hamiltonpfad in G
=> es existiert ein Hamiltonpfad von in G'
=> <> UHAMPATH

Allerdings verstehe ich nicht, warum dies funktionieren soll, da wir ja nur jeden Knoten praktisch verdreifachen und die Richtungen entfernen. Warum ist diese Verdreifachung notwendig?