NP-Vollständigkeit

Question 1

Ist das Problem einfach oder Schwer?

Finde den längsten, einfachen Weg in einem Graphen

Answer 1

schwer

Question 2

Ist das Problem einfach oder Schwer?

Finde den kürzesten, einfachen Weg in einem Graphen

Answer 2

O(|E|)

Question 3

Ist das Problem einfach oder Schwer?

Hamilton-Zyklus: einfacher Zyklus, der alle Knoten enthält

Answer 3

schwer

Question 4

Ist das Problem einfach oder Schwer?

Euler-Tour: Zyklus, der alle Kanten ein mal enthält

Answer 4

O(|E|)

Question 5

Ist das Problem einfach oder Schwer?

Clique: vollständiger Teilgraph mit k Knoten

Answer 5

schwer

Question 6

Ist das Problem einfach oder Schwer?

Independent Set: Teilgraph mit k Knoten ohne Kanten

Answer 6

schwer

Question 7

Ist das Problem einfach oder Schwer?

Färbbarkeit:adjazente Knoten haben unterschiedliche Farben.
* Färbbar mit zwei Farben?
* Färbbar mit drei Farben?

Answer 7

zwei: O(|E|)
drei: schwer

Question 8

Ist das Problem einfach oder Schwer?

PARTITION:geg.eineMengeganzerZahlen,Lässtsich die Menge in zwei Teilmengen gleicher Summe zerlegen?

Answer 8

schwer

Question 9

Welche Problemtypen existieren?

Answer 9

• Optimierungsprobleme
• Entscheidungsprobleme

Question 10

Was ist ein Optimierungsproblem?

Answer 10

finde eine gültige Lösung mit einem minimalen Wert bzgl. einer Bewertungsfunktion

Question 11

Was ist ein Entscheidungsproblem?

Answer 11

prüfe, ob eine gültige Lösung existiert

Question 12

Formuliere ein Entscheidungsproblem für ein Optimierungsproblem

k-Threshold-Problem

Answer 12

Gibt es eine Lösung für P mit Wert ≤ k?

Question 13

f: {0,1}* -> {0,1}* heißt polynomzeit-berechenbar
g.d.w. …?

Answer 13

ein Algorithmus A zur Berechnung von f existiert mit Laufzeit TA(n) = O(nk) für eine Konstante k

Question 14

Was ist die Komplexitätsklasse P?

Answer 14

Menge aller konkreten Entscheidungsprobleme die polynomzeit-berechenbar sind.

Question 15

Wann ist ein Optimierungsproblem in P?

Answer 15

Ein Optimierungsproblem f ist in P, g.d.w. zugehörige k-Threshold- Problem E_f in P ist.

Question 16

Wann ist ein abstraktes Entscheidungsproblem in P?

Answer 16

abstrakte Entscheidungsprobleme f sind in P, g.d.w. es eine Codierung polynomieller Länge gibt und das zugehörige konkrete Entscheidungsproblem ist in P

Question 17

Wann ist ein Problem polynomzeit-verifizierbar?

Answer 17

es existiert ein er Algorithmus A, der in polynomieller Zeit überprüft, ob die Lösung korrekt ist

Question 18

Was ist die Komplexitätsklasse NP?

Answer 18

Menge aller konkreten Entscheidungsprobleme, die polynomzeit-verifizierbar sind

Question 19

Was heißt NP-Vollständig?

Answer 19

Problem liegt in NP und ist NP-schwer

Question 20

Wann ist ein Optimierungsproblem NP-schwer?

Answer 20

wenn das zugehörige k-Threshold-Problem E_f NP-vollständig ist

Question 21

Wie funktioniert Polynomzeit-Reduktion?

Answer 21

Question 22

Beschreib das Satisfiability-Problem (SAT)

Answer 22

• np-vollständig

Question 23

Zeige SAT∈NP

Answer 23

Question 24

Nenn NP-vollständige Probleme

Answer 24

Question 25

Was ist VERTEX-COVER?

Answer 25

Knotenmenge V‘, |V‘| ≤ k, jede Kante ist zu mindestens einem Knoten in V‘ inzident

Question 26

Was ist 3-SAT?

Answer 26

Gibt es eine erfüllende Belegung für CNF Jede Klausel hat maximal 3 Literale

Question 27

Was ist HAM-Cycle?

Answer 27

Gibt es einen einfachen Zyklus, der alle Knoten enthält

Question 28

Was ist TSP?

Answer 28

Traveling Salesperson Problem (kürzeste Rundtour in einem vollständigen, kantengewichteten Graphen)

Question 29

Was ist das Triangle-TSP?

Answer 29

Traveling Salesperson Problem (kürzeste Rundtour in einem vollständigen, kantengewichteten Graphen) + Dreiecksungleichung

Question 30

Was ist eine k-Clique?

Answer 30

Question 31

Was ist das SUBSET-SUM Problem?

Answer 31