nur wieso gilt am ende Gleichheit zwischen TIME(2^O(log n)) und TIME(n)
This post has been edited 1 times, last edit by "Arne" (Feb 18th 2011, 9:20am)
This post has been edited 2 times, last edit by "Skuld" (Feb 20th 2011, 1:34pm)
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.
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.
This post has been edited 3 times, last edit by "Skuld" (Feb 20th 2011, 3:11pm)
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
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.
This post has been edited 1 times, last edit by "Arne" (Feb 20th 2011, 5:50pm)
@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.
This post has been edited 3 times, last edit by "Xular" (Feb 20th 2011, 7:13pm)