Rezepte

“Schreibe einen Algorithmus der das Problem löst und in Element von P ist”

1. Problem an Beispielen verdeutlichen

2. Algorithmus konstruieren

3. Korrektheit elräutern

4. Laufzeit berechnen und folgern er liegt in P

1. Problem liegt in NP über pm Reduktion, polynomielle Überprüfbarkeit, NTM

2. Problem ist NP-schwer über pm Reduktion

1. Bekanntes NP-schweres Problem B finden

2. Reduktionsfunktion f konstruieren, die Instanzen aus B auf A abbildet

3. Zeigen f ist in Polynomialzeit von DTM berechenbar

4. x e B <==> f(x) e A

1. ISMT (I -> genau angeben was x ist e N/R/Q & gerichtet oder ungerichteter Graph; S wie sehen lösungen aus/ Bedingungen notwendig?, M was wird gemessen, T)

2. Entscheidungsproblem dazu:

1. Instanzen und Maßfunktion einsetzen

2. Zeigen, dass PD => Problem & Problem => PD

=> Daraus folgt PD = Problem

• Es gibt ein Polynom p, sodass für alle |y| <= p(|x|) (wie lang ist eine Lösung im Verhältnis zur Instanz -> p angeben

• Polynomielle Laufzeit zur Überprüfung Lösung

• Maßfunktion in polynomieller Laufzeit

  
  

• X muss in NPO liegen

• DTM Algorithmus, der zeigt, dass es optimale Lösung in Polynomialzeit zu X gibt

• 
  

Entscheidungsproblem NP-Vollständig durch pm Reduktion