NP-Vollständigkeit

In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient lösen lässt.

Formal wird NP-Vollständigkeit nur für Entscheidungsprobleme definiert (mögliche Lösungen nur „ja“ oder „nein“), während man bei anderen Problemtypen von NP-Äquivalenz spricht (etwa bei Suchproblemen oder Optimierungsproblemen). Umgangssprachlich wird diese Unterscheidung jedoch oft nicht vollzogen, so dass man ganz allgemein von „NP-vollständigen Problemen“ spricht, unabhängig davon, ob ein Entscheidungsproblem vorliegt oder nicht. Dies ist möglich, da verschiedene Problemtypen ineinander überführbar (aufeinander reduzierbar) sind.

Ein Entscheidungsproblem ist NP-vollständig, wenn es

• in der Komplexitätsklasse NP liegt: Ein deterministisch arbeitender Rechner benötigt nur polynomiell viel Zeit, um zu entscheiden, ob eine vorgeschlagene Lösung eines zugehörigen Suchproblems tatsächlich eine Lösung ist, und
• zu den NP-schweren Problemen gehört: Alle anderen Probleme, deren Lösungen deterministisch in polynomieller Zeit überprüft werden können, können auf das Problem derart zurückgeführt werden, dass diese Rückführung auf einem deterministischen Rechner höchstens polynomielle Zeit in Anspruch nimmt. Man spricht von einer Polynomialzeitreduktion.

Die Klasse aller NP-vollständigen Probleme wird mit NP-C (complete) bezeichnet. Die Eigenschaften dieser und anderer Klassen werden in der Komplexitätstheorie erforscht, einem Teilgebiet der theoretischen Informatik.

NP-vollständige Probleme lassen sich vermutlich nicht effizient lösen, da ihre Lösung auf realen Rechnern viel Zeit in Anspruch nimmt. In der Praxis wirkt sich dies nicht in jedem Fall negativ aus, das heißt, es gibt für viele NP-vollständige Probleme Lösungsverfahren, anhand deren sie für in der Praxis auftretende Größenordnungen in akzeptabler Zeit lösbar sind.

Viele in der Praxis auftauchende und wichtige Probleme sind NP-vollständig, was NP-Vollständigkeit zu einem zentralen Begriff der Informatik macht. Weiter verstärkt wird diese Bedeutung durch das sogenannte P-NP-Problem:

1. Für kein NP-vollständiges Problem konnte bisher nachgewiesen werden, dass es in polynomieller Zeit lösbar wäre.
2. Falls nur ein einziges dieser Probleme in polynomieller Zeit lösbar wäre, dann wäre jedes Problem in NP in polynomieller Zeit lösbar, was große Bedeutung für die Praxis haben könnte (jedoch nicht notwendigerweise haben muss).

Seit der Einführung der NP-Vollständigkeit durch Cook wurde die Vollständigkeit zu einem allgemeinen Konzept für beliebige Komplexitätsklassen ausgebaut.