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

Schöne Ferien!
 

 

Zusammenhang der ganzen Komplexitätsklassen mit SAT/CLIQUE

–1 Punkt
78 Aufrufe

Ich habe den Zusammenhang der ganzen Komplexitätsklassen mit SAT/CLIQUE noch nicht verstanden. Wie stehen diese dazu? In welche Komplexitätsklassen teilt man diese zu und warum gilt: A <(pol) SAT nochmal?

Stimmt es, dass CLIQUE NP-schwer ist? Und dann auch SAT..

 

Gefragt 26, Nov 2014 in BER-AH von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte
 
Beste Antwort

Hallo,

Sat und Clique sind Probleme, die Komplexitätsklassen zugeordnet werden können(SAT NP-vollst., Clique NP-schwer, siehe dazu Vorlesungsfolien). Für diese Aufgabe muss man sich die Definition dieser Klassen genauer anschaun und der Reduzierbarkeit.

A<(pol) Sat gilt, da beide Probleme NP-vollst. sind und diese sich immer auf einander pol. reduzieren lassen.

Gruß,

Adam (Tutor)

 

Beantwortet 26, Nov 2014 von uafjv uafjv Tutor(in) (167,990 Punkte)  
Laut Wikipedia und co. ist sowohl SAT und ClIQUE NP-vollst. - Für uns gilt aber wie in den Vorlesungsfolien: SAT NP-vollst. und Clique NP-schwer??

EDIT: Auf Heimübungsblatt 4 wird auch nur erwähnt, dass man zeigen soll: CLIQUE ist NP-vollständig
In der Vorlesung wird lediglich die Reduktion von 3-SAT nach Clique durchgeführt, was nur zeigt, dass Clique NP-schwer ist (mehr können wir daraus nicht folgern). Auf dem Heimübungsblatt wird dann ein Schritt weiter gegangen und gezeigt, dass Clique auch in NP liegt, d.h. dass Clique NP-vollständig ist.

Ich hoffe, dass das jetzt zum Verständnis beigetragen hat.

Viele Grüße

Friederike Pfeiffer-Bohnen und Lukas König
...