NP-Completeness
Ein NP-vollständiges Problem gehört zu NP, und jedes NP-Problem lässt sich polynomial darauf reduzieren; dies sind die schwersten Probleme in NP.
Zweck
Die Komplexitätshierarchie verstehen und unhandhabbare Probleme erkennen.
Mechanismus
NP: in Polynomialzeit verifizierbar. NP-schwer: Jedes NP-Problem reduziert sich darauf. NPC=NP∩NP-schwer. Hat irgendein NPC-Problem eine Polynomialzeit-Lösung, gilt P=NP. Klassiker: SAT, TSP, Knotenüberdeckung.
Anwendungsfälle
- Komplexitätsanalyse
- Bewertung der Problemschwere
- Reduktionsbeweise