Hallo,
Ich muss eine kleine Aufgabe lösen, ich weiss allerdings nicht wie ich anfangen soll… 
Ich hoffe deshalb jemand aus diesem Forum kann mir ein wenig auf die Sprünge helfen?
Also zur Aufgabe:
–
Beweisen Sie, dass das folgende Problem, welches wir als Gadget-Spiel bezeichenen werden, NP-vollständig ist.
Gadget ist ein Spiel, wo der Spieler einen Satz von Bauteilen erh+alt (über Bilder)
und ein Ziel von Gadgets (auch über Bilder). Der Spieler sollte jedes der spezifizierten Gadgets durch die Bauteile erstellen, in dem er ein Teil nach dem anderen zusammensetzt, mit so wenigen Schritten wie möglich.
Jedes Gadget besteht aus einem Bauteil namens „Stromversorgung“ (das eines der gegebenen Teile ist) und
zwei weiteren Teilen. Die Kombination von zwei Teile oder ein Teil mit etwas schon
montiertem zählt als ein Schritt. Es ist kostenlos ein Teil von etwas bereits Montiertem zu entfernen, sofern die Kombination des übriggebliebene Gadget vom Spieler bereits zuvor zusammen gesetzt worden ist.
Beispiel: Der Spieler hat die Teile A (der Stromversorgung), B, C, D und E, und muss
die Gadgets (A, B, C), (A, B, D), (A, B, E) und (A, C, E) erstellen. Dies kann er mit 6 Schritten
(niedrige Werte sind gut) wie folgt: Kombinieren von A und B um (A, B) zu erhalten. Kombiniere (A, B)
mit C um (A, B, C) zu erhalten. Entferne C von (A, B, C) um wieder (A, B) zu erhalten. Dieser Schritt war kostenlos und zählt nicht mit, da der Spieler bereits zuvor (A, B) zusammengebaut hatte.
Kombiniere (A, B) und D um (A, B, D) zu erhalten. Entfernen von D ist dann wieder kostenlos.
Kombiniere dann (A, B) und E um (A, B, E) zu erhalten. Entferne E (kostenlo)s und entferne B (kostenlos).
Kombiniere A und E um (A, E) zu erhalten. Kombiniere (A, E) mit C um (A, C, E) zu erhalten. Beachte, dass
die Reihenfolge der Teile in den Gadgets keine Rolle spielt, wie beim letzten Gadget zu sehen war.
Auch die Gadgets an sich brauchen sie nicht in der angegebenen Reihenfolge erstellt zu werden. Es wäre also in Ordnung (A, B, D) vor (A, B, C) zu erstellen.
Wir könnten allerdings NICHT B von (A, B, E) kostenlos entfernen, weil (A, E) nicht alleine vorher zusammengesetzt war.
Das Gadget-Spiel Problem ist: eine Reihe von Teilen und eine Reihe von Ziel-Gadgets sei gegeben, ist es möglich die Gadgets mit höchstens L „Schritten“ zusammen zusetzen??
Ein Teil Ihrer Beweises sollte eine Reduktion von Vertex Cover Problem sein.
Ich weiss, dass ich erst ein Certificate (quasie die Lösung wie viele Schritte benutzt werden) finden muss und zeigen muss, dass man dieses Certificate in Polynomieller Zeit überprüfen kann. Damit zeige ich dass das Spiel in NP ist.
Als Certificate wähle ich sämtliche Gadgets die erstellt werden, also auch die „Zwischen-Gadgets“, um zu den Ziel-Gadgets zu gelangen. Im Beispiel oben wären diese also (A, B), (A, E), (A, B, C), (A, B, D), (A, B, E). Die Anzahl dieser Gadgets ist die Anzahl der Schritte die getätigt wurden insgesamt. Nun kann man überprüfen, ob man von den einzelnen Bauteilen die ersten Gadgets (mit der Länge zwei, also (A,B), (A,E)) zusammensetzen kann. Danach überprüft man ob man von den Gadgets mit der Länge zwei zu den Ziel-Gadgets (mit der Länge drei) kommen kann.
Dies kann in poly-zeit überprüft werden => Gadget-Spiel liegt in NP.
Ist das richtig soweit?
Nun zur Reduktion von Vertex-Cover zu diesem Spiel. Ich muss das Spiel ja irgendwie als ein Graph-Problem betrachten. Doch hier versage ich kläglich. Ich hab einfach keine Ahnung wie ich das Vertex-Cover Problem übersetzen kann, so dass man mithilfe einer Lösung von Vertex-Cover auch eine Lösung für das Gadget-Spiel finden kann.
Ich weiss, es ist ziemlich viel Text und sicher nicht einfach zu verstehen. Ich hoffe aber trotzdem dass mir jemand weiter helfen kann.