NP-Vollständigkeit

Question 1

Polynomzeit-Reduktion - Definition

Answer 1

Question 2

Transitivität von Polynomzeit-Reduktion

Answer 2

Question 3

Polynomzeitreduktion - Lemma

Answer 3

Question 4

Was ist ein “Vertex Cover” bei einem Graphen?
Eingabe: unverrichteter Graph G, Zahl k > 0

Answer 4

Gibt es k Knoten in G, sodass jede Kante in G mindesten eine dieser k Knoten als Endpunkte hat?

Question 5

Was ist ein “Independent Set” bei einem Graphen?
Eingabe: unverrichteter Graph G, Zahl k > 0

Answer 5

Gibt es k Knoten in G, sodass keine 2 dieser k Knoten mit einer Kante verbunden sind?

Question 6

Was ist ein “Dominating Set”bei einem Graphen?
Eingabe: unverrichteter Graph G, Zahl k > 0

Answer 6

Gibt es k Knoten in G, sodass jeder andere Knoten eine Kante zu mindestens einem dieser Knoten hat?

Question 7

Vertex Cover und Independent Set - Theorem

Answer 7

Question 8

NP-schwer und NP-vollständig - Definition

Answer 8

Question 9

NP-schwer - Anschaulich

Answer 9

NP-schwere Sprachen sind “mindesten so schwer” zu entscheiden wie jede Sprache in NP

Question 10

NP-vollständig - Anschaulich

Answer 10

NP-vollständige Sprachen sind “genau so schwer” wie jede NP-vollständige Sprache

Question 11

NP-schwer - Lemma

Answer 11

Question 12

NP-Vollständigkeit - Theorem

Answer 12

Question 13

SAT Problem

Answer 13

Question 14

Satz von Cook und Levin (Theorem)

Answer 14

SAT ist NP-vollständig