Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Warum ist Clique NP schwer?

+1 Punkt
70 Aufrufe

Im Aufgabenteil c zeigen wir, das Clique NP schwer ist.

Im Heimübungsblatt 4 A1 zeigen wir, das Clique NP schwer ist.

Sind sowohl SAT als auch Clique NP schwer und da sie in NP liegen auch beide NP vollständig?

 

Gefragt 23, Sep 2015 in 2014-H-05 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

+1 Punkt
Hallo,

laut Definition ist ein Problem NP-vollständig, genau dann wenn das Problem NP-schwer ist und in NP liegt.

In der Vorlesung wurde gesagt, dass das SAT Problem das erste Problem war für das die NP-Vollständigkeit nachgewiesen wurde (von Cook).

Desweiteren wurde die NP-Vollständigkeit von CLIQUE gezeigt, durch die Idee der Reduktion von 3-SAT (von dem wir wissen, dass es NP-vollständig ist) auf CLIQUE.

Viele Grüße

Julian (Tutor)
Beantwortet 23, Nov 2015 von uldbw uldbw Tutor(in) (100,600 Punkte)  
...