Cliquenproblem in NP |
| 15.01.2011, 02:12 | Auf diesen Beitrag antworten » |
| Ina | Cliquenproblem in NP Meine Frage: Hallo! Ich muss beweisen, dass das Cliquenproblem NP-vollständig ist. NP-Härte habe ich schon bewiesen, aber mein Beweis dafür, dass es in NP ist hinckt und ich hätte auch gerne ein Beispiel für einen Graphen, der es erfüllt. Cliquenproblem: Gegeben ist ein Graph G=(V,E) und eine natürliche Zahl k. Gibt es eine Clique der Größe k in G? Clique: Zusammenhängender Teilgraph; je zwei Knoten sind miteinander verbunden. Meine Ideen: Hat man eine Teilmenge von V erraten, für die gilt, dass die Größe der Teilmenge = k ist, ist es offensichtlich, dass man sein Ergebnis in ploynomieller Zeit verifizieren kann. Zumindest empfinde ich das so. Allerdings ist das noch kein wirklicher Beweis, dass es so ist und ein Bsp. wäre auch nicht schlecht... |
|
|
|
| 16.01.2011, 19:30 | Auf diesen Beitrag antworten » |
| Ibn Batuta | Sagt dir 3SAT etwas? Wenn ja, reduziere es auf 3SAT. Dann ist der Beweis nicht so schwer. Ibn Batuta |
| 26.02.2011, 20:03 | Auf diesen Beitrag antworten » |
| Hubert1965 | Wenn ich mich nicht sehr irre, ist ein Problem exakt genau dann NP-vollständig, wenn es einen Algorithmus gibt, mit dem die Parameter dieses Problems in polynomieller Zeit in die Parameter eines anderen Problems umgewandelt werden können, von dem bereits bekannt ist, dass es NP-vollständig ist. Es gibt derzeit 21 Probleme, für die die NP-vollständigkeit bereits beweisen ist: http://de.wikipedia.org/wiki/Karps_21_NP...ndige_Probleme. Das Cliquen-Problem ist in dieser Liste enthalten. Wenn es dir gelingt, dieses Problem z.B. auf http://de.wikipedia.org/wiki/Erfüllbarke...r_Aussagenlogik zurückzuführen, hast du den Beweis erbracht. |
|
|