Registrierung Kalender Mitgliederliste Teammitglieder Suche Häufig gestellte Fragen Zur Startseite

Informatiker Board » Themengebiete » Theoretische Informatik » Berechenbarkeits- und Komplexitätstheorie » Cliquenproblem in NP » Antwort erstellen » Hallo Gast [Anmelden|Registrieren]

Antwort erstellen
Benutzername: (du bist nicht eingeloggt!)
Thema:
Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

Smilies: 21 von 33
smileWinkDaumen hoch
verwirrtAugenzwinkerngeschockt
Mit ZungeGottunglücklich
Forum Kloppebösegroßes Grinsen
TanzentraurigProst
TeufelSpamWillkommen
LehrerLOL HammerZunge raus
Hilfe 
aktuellen Tag schließen
alle Tags schließen
fettgedruckter Textkursiver Textunterstrichener Text zentrierter Text Hyperlink einfügenE-Mail-Adresse einfügenBild einfügen Zitat einfügenListe erstellen CODE einfügenPHP CODE farbig hervorheben
Spamschutz:
Text aus Bild eingeben
Spamschutz

Die letzten 3 Beiträge
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.
Ibn Batuta

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


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