Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Berechenbarkeits- und Komplexitätstheorie (http://www.informatikerboard.de/board/board.php?boardid=15)
----- Cliquenproblem in NP (http://www.informatikerboard.de/board/thread.php?threadid=844)


Geschrieben von Ina am 15.01.2011 um 02:12:

  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...



Geschrieben von Ibn Batuta am 16.01.2011 um 19:30:

 

Sagt dir 3SAT etwas? Wenn ja, reduziere es auf 3SAT. Dann ist der Beweis nicht so schwer.


Ibn Batuta



Geschrieben von Hubert1965 am 26.02.2011 um 20:03:

 

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-vollstä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üllbarkeitsproblem_der_Aussagenlogik zurückzuführen, hast du den Beweis erbracht.


Forensoftware: Burning Board, entwickelt von WoltLab GmbH