P und NP (5) < Training < Informatik < Vorhilfe
|
| Status: |
(Übungsaufgabe) Aktuelle Übungsaufgabe  (unbefristet) | | Datum: | 06:44 Do 09.02.2006 | | Autor: | mathiash |
| Aufgabe | Wir betrachten NP-Härte und NP-Vollständigkeit bezüglich der polynomiellen KarpReduktion [mm] \leq_m^p [/mm] (die aus Sicht vieler ''normale'' Reduktion).
(a) Zeige (ohne Buch etc.): SAT und 3SAT sind NP-vollständig.
(b) Zeige (wieder ohne Buch): CLIQUE und VERTEX COVER sind NP-vollständig.
(c) Zeige: B-VC (B-Bounded Degree Vertex Cover) ist NP-vollständig [mm] (B\geq [/mm] 4).
Dabei ist B-VC die Restriktion von VC (Vertex Cover) auf Graphen mit Maximalgrad
B.
(d) Zeige: 2SAT liegt in P.
(e) Zeige: 2-VC liegt in P.
(f) Zeige: Das Halteproblem K ist NP-hart bezüglich [mm] \leq_m^p, [/mm]
aber nicht NP-vollständig. |
Hallo zusammen,
es werden Schritt fuer Schritt noch weitere derartige Aufgaben kommen.
Gruss,
Mathias
|
|
|
