Nächste Seite: Die große Frage der Aufwärts: Hauptseite Theorie Vorherige Seite: Platzkomplexität   Inhalt

NPC Beweise

---

Unterabschnitte

• Die große Frage der Informatiker P=NP oder PNP?
• Polynomielle Reduzierbarkeit
• NP-hart, NP-vollständig
  • NP-hart
  • NP-vollständig
  • Sätze
  
  
• Aussagelogik
• Satz von Cook
  • Satz
  • Beweis
  • Korrektheit
  • Kosten
  
  
• Prinzipielle Techniken für NP-Vollständigkeitsbeweise
  • Spezialisierung
  • Lokale Ersetzung
  • Transformation mit verbundenen Komponenten
  
  
• Einige NP-Vollständigkeitsbeweise
  • SAT 3SAT (lokale Ersetzung)
  • 3SAT CP (Transformation)
  • 3SAT RP (Transformation sowie auch Spezialisierung)
  • 0/1 Integer Linear Programming (Transformation)
  • Weitere NPC-Beweise
  
  
• coNP
• PSPACE-Vollständigkeit
• Zusammenfassung

---