NP Cliquenproblem < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 12:15 Di 23.01.2007 | | Autor: | tommy987 |
| Aufgabe | Beweise, dass das Cliquenproblem NP-vollständig ist. Zwei Anmerkungen dazu:
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.
Die Art des Beweises bleibt Dir freigestellt. Es bietet sich z. B. ein Reduktionsbeweis eines als NP-vollständig bekannten Problems an. Wichtig dabei ist, dass Du die verwendete Literatur korrekt zitierst! |
NP Probleme sind ja eigentlich Klassen von Entscheidungsproblemen, oder? Nur welchen Ansatz nehme ich dazu, um es zu lösen?
lg Thomas
|
|
| |
|
Hallo,
also NP ist eine Klasse von Entscheidungsproblemen. Und nicht jedes Problem aus NP ist eine Klasse von Entscheidungsproblemen.
Das Stichwort ist polynomielle Reduktion. Du nimmst Dir ein Problem aus NPC (d.h. die Klasse der NP-vollständigen Entscheidungsprobleme) und reduzierst dieses auf Clique. Wenn Du das mit einer polynomiellen Reduktion hinbekommst, gilt offentlichtlich (jedenfalls wenn man sich die Definitionen anschaut) dass Clique NP-hart ist. Dann muss man nurnoch Zeigen, dass es auch in NP liegt.
--
Matthias
|
|
|
|
