Diskussion:Cliquenproblem

Wäre nett, wenn man dieses ordentlich machen könnte und auch für nicht IT-ler visualisieren.

• Ich habe es probiert. Die Graphen waren allerdings doch etwas komplizierter als erwartet :) MichaelGl
• Definition von NP-vollständig ist doch:

  1. Ein NP-vollständiges lässt sich auf Problem zurückführen --> wurde gezeigt
  2. Problem in NP --> Müsste dies nicht auch in dem Beweis gezeigt werden?

Antwort zu Punkt 2: Ja muesste es. Dies ist jedoch trivial.

Beweisskizze: Zu zeigen das ein Graph G={V,E} eine Clique der groesse |V| enthaelt ist in Linearzeit moeglich, da dann jedes v \in in V |V|-1 ausgehende Kanten haben muss. Um nun zu entscheiden ob G eine Clique der Groesse k hat nimmt man einfach alle k-elementigen Teilmengen aus V und ueberprueft ob dieser Graph vollstaendig ist. K elementige Teilmengen gibt es |V| ueber k <= 2^|V|. Also hat dieser Algorithmus eine exponentielle Laufzeit und ist damit in NP. --89.246.176.48 05:14, 20. Nov. 2010 (CET)

Etwas präziser: Nicht weil dieser Algorithmus exponentielle Laufzeit hat ist das Problem in NP, sondern weil man - wie dargestellt - nach dem Raten einer möglichen Lösung deren Richtigkeit in Polyzeit überprüfen kann.

(Es ist ein verbreiteter Irrglaube das NP für "not polynomial time" stehen würde, stattdessen meint die Abk. "nondeterministic polynomial time".) Liebe Grüße -- 2001:638:807:20D:F011:73A9:DF4C:105A 13:18, 5. Feb. 2016 (CET)

PS: Außerdem braucht das Testen auf Vollständigkeit quadratische (statt lineare) Zeit, für jedes Paar von Knoten muss die Existenz einer verbindenden Kante geprüft werden; der bloße Ausgangsgrad ist nicht aussagekräftig. --2001:638:807:20D:F011:73A9:DF4C:105A 13:22, 5. Feb. 2016 (CET)

Lösung?

Ich hab da mal eine Frage. Ich bin hier: http://www.vinnica.ua/~aplot/solver.html auf die Behauptung gestossen, dass Dr. Plotnikov das Problem auf Polinonielle Laufzeit reduzieren konnte, oder doch nicht? Das würde doch sonst bedeuten, dass NP-Vollständig=P ist.