Problemreduktion und Zusammenfassung

Das Hamiltonkreis-Problem ist NP-vollständig. Erläutern Sie ausführlich was das bedeutet. Dabei sollen mindestens folgende Aspekte und Begriffe thematisiert werden:

  • Klasse P und Klasse NP
  • Probleme in NP und NP-vollständige Probleme
  • SAT
  • Karp’s NP-vollständige Probleme
  • Problemreduktion
  • Praktisch lösbare Probleme
  • Komplexität eines Algorithmus und Komplexität eines Problems
  • Praktische Relevanz

Tipps und hilfreiche Recherchepunkte:

  • Was hat multiplizieren und addieren mit Problemreduktion zu tun?
  • Mengendiagramm für Algorithmen, falls P=NP und falls P¹NP
  • Gibt es Probleme, die nicht in NP sind?

Hilfreich können auch die beiden folgenden Grafiken sein:

Ein Kommentar zu „Problemreduktion und Zusammenfassung

Schreibe einen Kommentar