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“