Fachrat Informatik - Forum

Was genau bezweckst Du mit der großen Vereinigung vor NSPACE(log n)?

Du meinst also:


Wenn Du jetzt noch für die beiden Inklusionsbeziehungen begründest warum das gelten soll, dann geht das.

Bis zu TIME(2^O(log n)) verstehe ich es noch und das TIME(n) Teilmenge von TIME(2^n) ist mir auch klar, nur wieso gilt am ende Gleichheit zwischen TIME(2^O(log n)) und TIME(n).

Quoted from "Shorty86"

nur wieso gilt am ende Gleichheit zwischen TIME(2^O(log n)) und TIME(n)

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

Hallo,
ne Frage zum Vorgehen, wenn man zeigen soll, dass ein Problem in NP liegt. Ich schaue mir gerade aus Übung 5 die Aufgabe 2 an:

COLORABILITY := {<G, k> | k N und G ist ein k-färbbarer ungerichteter Graph}, wobei k-färbbar bedeutet, dass der Graph mit k Farben so färbbar ist, dass ein Knoten und alle seine Nachbarknoten unterschiedliche Farben besitzen.

Ich würde zum überprüfen nun sagen ich bekomme als Eingabe <G, k> und die Knotenmenge X aller Knoten in G.
Nun gucke ich für jeden Knoten ob er höchstens k-1 Nachbarknoten hat (da es sonst ja schon mal nicht sein kann, dass sie jeweils unterschiedlich gefärbt sind). Wenn nein, ablehnen. Wenn doch, gucke ich für jeden Knoten bei seinen Nachbarknoten, ob sie unterschiedlich gefärbt sind. Wenn nein, ablehnen, sonst akzeptieren.
Das wäre ja eine Überprüfung in Polynomialzeit, ist das (auch formal) korrekt so?

Und noch eins zur NP vollständigkeit, Übung 9 Aufgabe 2 mit EVEN-HAMCIRC (also Graph, der einen Hamilton-Kreis gerader Länge enthält).
1. Ist NP, mit Eingabe Graph und Startknoten: Überprüfen, ob der Pfad vom Startknoten zu sich selber jeden anderen Knoten genau ein Mal besucht und gerade Länge hat.
2. Reduktion von HAMCIRC mit der Funktion, die nichts tut falls der HAMCIRC bereits gerade Länge hat und ansonsten einen Knoten an beliebiger Stelle hinzufügt, bspw. zwischen Knoten1 und Knoten2, sodass eine Kante von Knoten1 zu KnotenX und eine von KnotenX zu Knoten2 hinzugefügt wird. Somit wurde ein EVEN-HAMCIRC erstellt.

Richtig so? Das kommt mir ein bisschen zu simpel vor, mein Ansatz.

Quoted from "Skuld"

COLORABILITY := {<G, k> | k N und G ist ein k-färbbarer ungerichteter Graph}, wobei k-färbbar bedeutet, dass der Graph mit k Farben so färbbar ist, dass ein Knoten und alle seine Nachbarknoten unterschiedliche Farben besitzen.

Ich würde zum überprüfen nun sagen ich bekomme als Eingabe <G, k> und die Knotenmenge X aller Knoten in G.
Nun gucke ich für jeden Knoten ob er höchstens k-1 Nachbarknoten hat (da es sonst ja schon mal nicht sein kann, dass sie jeweils unterschiedlich gefärbt sind). Wenn nein, ablehnen. Wenn doch, gucke ich für jeden Knoten bei seinen Nachbarknoten, ob sie unterschiedlich gefärbt sind. Wenn nein, ablehnen, sonst akzeptieren.
Das wäre ja eine Überprüfung in Polynomialzeit, ist das (auch formal) korrekt so?

Es fehlt noch die Begründung warum das ganze in Polynomialzeit funktioniert. Ansonsten isses okay.

Quoted from "Skuld"

Und noch eins zur NP vollständigkeit, Übung 9 Aufgabe 2 mit EVEN-HAMCIRC (also Graph, der einen Hamilton-Kreis gerader Länge enthält).
1. Ist NP, mit Eingabe Graph und Startknoten: Überprüfen, ob der Pfad vom Startknoten zu sich selber jeden anderen Knoten genau ein Mal besucht und gerade Länge hat.
2. Reduktion von HAMCIRC mit der Funktion, die nichts tut falls der HAMCIRC bereits gerade Länge hat und ansonsten einen Knoten an beliebiger Stelle hinzufügt, bspw. zwischen Knoten1 und Knoten2, sodass eine Kante von Knoten1 zu KnotenX und eine von KnotenX zu Knoten2 hinzugefügt wird. Somit wurde ein EVEN-HAMCIRC erstellt.

Richtig so? Das kommt mir ein bisschen zu simpel vor, mein Ansatz.

Bei 1. meinst Du dann wohl (Du hast es nicht geschrieben), dass auch der Pfad Teil der Eingabe ist?
Bei 2. musst Du mir erstmal begründen wieso deine Reduktionsfunktion in Polynomialzeit berechenbar ist. Das sehe ich jedenfalls nicht.

Quoted from "Arne"

Bei 1. meinst Du dann wohl (Du hast es nicht geschrieben), dass auch der Pfad Teil der Eingabe ist?
Bei 2. musst Du mir erstmal begründen wieso deine Reduktionsfunktion in Polynomialzeit berechenbar ist. Das sehe ich jedenfalls nicht.

Zu 1., hast recht, den hab ich vergessen.

Zu 2., naja, man geht ja nur den Circle ein Mal durch um zu zählen, also in O(n). Wenn es nun ungerade ist, fügt man einen Knoten ein, also in O(1). Oder lieg ich gedanklich gerad völlig daneben?

Quoted from "Skuld"

Zu 2., naja, man geht ja nur den Circle ein Mal durch um zu zählen, also in O(n). Wenn es nun ungerade ist, fügt man einen Knoten ein, also in O(1). Oder lieg ich gedanklich gerad völlig daneben?

Bei Reduktionen funktioniert das prinzipiell doch so: Du bekommst in unserem Fall als Eingabe eine Instanz von HAMCIRC und sollst das ganze abbilden auf EVEN-HAMCIRC. Sprich Du bekommst einen Graphen G und eine natürliche Zahl k und sollst dann (in Polynomialzeit) einen Graphen G' ausgeben (also formal f(<G,k>)=G'), so dass zusätzlich <G,k> in HAMCIRC gdw. f(<G,k>) in EVEN-HAMCIRC gilt. Wo nimmst Du da den "Circle" her?

Quoted from "Arne"

Quoted

Zitat von »Skuld«



COLORABILITY := {<G, k> | k N und G ist ein k-färbbarer ungerichteter Graph}, wobei k-färbbar bedeutet, dass der Graph mit k Farben so färbbar ist, dass ein Knoten und alle seine Nachbarknoten unterschiedliche Farben besitzen.

Ich würde zum überprüfen nun sagen ich bekomme als Eingabe <G, k> und die Knotenmenge X aller Knoten in G.
Nun gucke ich für jeden Knoten ob er höchstens k-1 Nachbarknoten hat (da es sonst ja schon mal nicht sein kann, dass sie jeweils unterschiedlich gefärbt sind). Wenn nein, ablehnen. Wenn doch, gucke ich für jeden Knoten bei seinen Nachbarknoten, ob sie unterschiedlich gefärbt sind. Wenn nein, ablehnen, sonst akzeptieren.
Das wäre ja eine Überprüfung in Polynomialzeit, ist das (auch formal) korrekt so?

Es fehlt noch die Begründung warum das ganze in Polynomialzeit funktioniert. Ansonsten isses okay.

Muss man da tatsächlich nur so wenig ins Detail gehen in der Klausur? In der Übung war das teilweise ausformuliert, teilweise nicht...

D.h. reicht "Wenn doch, gucke ich für jeden Knoten bei seinen Nachbarknoten, ob sie unterschiedlich gefärbt sind."
statt z.B.
1. prüfe (...)
2. for v in V
2.1 for e = (m,n) in E
2.1.1 if (v == m) then if (färbung(v) == färbung(n)) then verwerfe
2.1.2 if (v == n) then if (färbung(v) == färbung(m)) then verwerfe
3. akzeptiere

@Xular: Es hat halt alles Vor- und Nachteile: Bei deiner Lösung musst Du nicht viel begründen warum die Laufzeit polynomiell ist, hier musst Du nur fix die Schleifen in die Laufzeit-Betrachtung einbeziehen. Bei Skuld, der es halt eher umgangssprachlicher gemacht hat, muss dann natürlich mehr Erklärungsaufwand bei der Laufzeitabschätzung reingesteckt werden. Die Erkenntnis ist allerdings im Endeffekt die selbe, die ihr beide bekommen und rüberbringen müsst.

Ganz so umgangssprachlich hätte ich es in der Klausur natürlich nicht formuliert, schon ein wenig algorithmischer, sodass eine Laufzeitbetrachtung leichter abzusehen ist, wenn auch nicht ganz so ausführlich wie von dir umrissen, Xular.

@Arne: Wieso bekomme ich <G, k> als Eingabeinstanz? HAMCIRC ist doch so definiert, dass ich einen Graphen <G> habe, in dem ein Hamilton Kreis existiert. Soll heißen diesen Graphen bekomme ich als Eingabeinstanz. Meine Funktion sieht so aus, dass ich eben diesen Kreis (der ja existiert in der Eingabeinstanz?) durchlaufe und dann ggf. einen Knoten hinzufüge.

Quoted from "Skuld"

@Arne: Wieso bekomme ich <G, k> als Eingabeinstanz? HAMCIRC ist doch so definiert, dass ich einen Graphen <G> habe, in dem ein Hamilton Kreis existiert. Soll heißen diesen Graphen bekomme ich als Eingabeinstanz. Meine Funktion sieht so aus, dass ich eben diesen Kreis (der ja existiert in der Eingabeinstanz?) durchlaufe und dann ggf. einen Knoten hinzufüge.

Du hast natürlich recht, <G> ist die Eingabe-Instanz. Habe ich durcheinander gebracht. Wie willst Du denn in P-Zeit feststellen, dass der Graph einen solchen Kreis besitzt? Ob die Instanz positiv oder negativ ist bzgl. der Sprache, dass sollst Du ja gar nicht beantworten. Genau darum geht es ja bei Reduktionen! Wenn <G> in HAMCIRC ist, dann muss f(<G>) in EVEN-HAMCIRC sein. Wenn <G> nicht in HAMCIRC ist, darf f(<G>) auch nicht in EVEN-HAMCIRC sein! D.h. der Funktion f ist es in der Regel egal ob die Instanz zu HAMCIRC gehört oder nicht. Sie macht einfach "irgendwelche" Veränderungen (meine Frage wäre da: welche?) an dem Graphen und diese Gültigkeitseigenschaft (ich nenne das mal so jetzt in Bezug auf die beiden Sprachen) bleibt immer bestehen. Wenn f nun zudem in P-Zeit berechenbar ist, dann ist das eine gültige P-many-one Reduktion, die wir suchen.

f: G ->
{ <G> , falls |V| gerade }
{ <G'> | mit G' = (V + vneu, E + (vstart,vneu) + (vneu,vstart+1) \ (vstart,vstart+1) ), falls |V| ungerade }

Reicht das schon so? (Man stelle sich das ganze mit ner schönen großen "{" vor - ich hab kA von latex )

edit: Laufzeit ist natürlich trivial - es werden nur 2 Kanten und ein Knoten hinzugefügt und eine Kante entfernt (oder nichts gemacht), also wohl in O(|V|) = O(n) lösbar, wenn man das zählen von allen Knoten mit einbezieht...

edit2: Eigentlich ist es egal, ob ein hamiltonscher Kreis besteht, nur die Knotenanzahl muss gerade sein, oder? (Habs mal in die Richtung angepasst).

Was ist vstart und was ist vstart+1?

Der erste und zweite Knoten im Array/Vektor V ... Kann man wohl auch anders nennen, ich hab sie so genannt als Startpunkt für den hamiltonschen Kreis, wobei der ja eigentlich keinen Startpunkt braucht...

Inwiefern ist es nötig die Kante (v_start, v_start+1) zu löschen? In dem Zusammenhang wären Erklärungen nötig.
Außerdem müsstest Du jetzt noch die Korrektheit Deiner Reduktion begründen. Sprich wenn G einen Hamiltonschen Kreis hat, hat G' einen Hamiltonschen Kreis gerader Länge. Und wenn G keinen Hamiltonschen Kreis hat, dann hat G' auf keinen Fall einen Hamiltonschen Kreis gerader Länge.

Hm, hab ich wohl nen Denkfehler drin, man darf nicht einfach Kanten hinzufügen, sondern muss eine alte Kante aufsplittern...
Also
f: G ->
{ <G> , falls |V| gerade }
{ <G'> | mit G' := (V + v_neu, E'), falls |V| ungerade }
mit E' := (E + (m, v_neu) + (v_neu, n) \ e)
mit e := (m,n) = erste Kante in E

Ob die Kante e am Ende entfernt werden -muss- ist mir gerade selber nicht ganz klar aber schaden tut es nicht.
Wenn man sie nicht entfernt hat das vermutlich keine Auswirkungen auf HAMCIRC, da jeder Knoten sowieso nur einmal besucht werden darf - diese extra Kante also einfach nicht benutzt wird vom Algo...
Andere Algorithmen würden da wohl Probleme mit bekommen, wenn man sie nicht entfernt, bspw einer, der alle Kanten abläuft..

Für die Begründung der Korrektheit reicht dann ja schon dieser Standardsatz, den du in deinem letzten Post geschrieben hast, richtig? Bzw etwas formaler mit "=>" und "<=".

Du musst ja schon argumentieren und nicht nur die Definition aufschreiben, so wie ich das oben gemacht habe. Das wäre dann zu wenig, insbesondere deshalb, weil Du Dir ja dann auch nicht genug Gedanken machst und mehr so "in's Blaue schießt" nach dem Motto "wird schon stimmen"; siehe Dein erster Versuch und auch der nächste klappt wieder nicht. Wie willst Du sicher stellen, dass gerade diese "erste" Kante in E genau für den Hamiltonschen Kreis benutzt wird? Könnte ja sein, dass die gar nicht benutzt wird und daher irrelevant ist...