ein-handwerker.de

NP-Vollständigkeit

26.05.2012 @ 21:49, Chricho,

miniatur|[[Mengendiagramm der möglichen Beziehungen zwischen P, NP und den Mengen der NP-schweren und NP-vollständigen Probleme.]]
In der Informatik bezeichnet man ein Problem als NP-vollständig (nichtdeterministisch-polynomiell vollständig), wenn
* ein �60�deterministisch�61� arbeitender Rechner nur polynomiell viel Zeit benötigt, um zu entscheiden, ob eine vorgeschlagene Lösung tatsächlich eine Lösung ist und

* wenn alle anderen Probleme, deren Lösungen deterministisch in polynomieller Zeit überprüft werden können, auf das Problem derart zurückgeführt werden können, dass diese Rückführung auf einem deterministischen Rechner höchstens polynomielle Zeit in Anspruch nimmt. Man spricht von einer Polynomialzeitreduktion.

Der erste der beiden Punkte drückt aus, dass das Problem in der Komplexitätsklasse NP liegt. Der zweite Punkt drückt aus, dass das Problem zu den sogenannten NP-schweren Problemen gehört.

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

Eine wesentliche Eigenschaft NP-vollständiger Probleme ist, dass sie sich vermutlich nicht effizient lösen lassen, dass also ihre Lösung auf realen Rechnern viel Zeit in Anspruch nimmt. In der Praxis wirkt sich diese Eigenschaft nicht in jedem Fall negativ aus, das heißt, es gibt für viele NP-vollständige Probleme Lösungsverfahren, anhand derer 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:
# Für kein NP-vollständiges Problem konnte bisher nachgewiesen werden, dass es in polynomieller Zeit lösbar wäre.

# 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.

Geschichte

Der Begriff der NP-Vollständigkeit wurde 1971 von Stephen A. Cook in seinem heute so genannten Satz von Cook eingeführt. Darin zeigte er, dass SAT NP-vollständig ist und somit ein Problem existiert, welches der Definition der NP-Vollständigkeit genügt. Heute existieren deutlich einfachere konstruktive Nachweise für die Existenz solcher Probleme, allerdings sind die dafür verwendeten Sprachen sehr künstlich. Cooks Verdienst besteht also auch darin, für eine besonders interessante Sprache diesen Nachweis erbracht zu haben.

Aufbauend auf der Arbeit von Cook konnte Richard Karp im Jahre 1972 eine weitere bahnbrechende Arbeit vorlegen, die der Theorie der NP-Vollständigkeit zu noch größerer Popularität verhalf. Karps Verdienst besteht darin, die Technik der Polynomialzeitreduktion konsequent genutzt zu haben, um für weitere 21 populäre Probleme die NP-Vollständigkeit nachzuweisen.

Definition

Ein Problem (genauer: ein Entscheidungsproblem) L heißt NP-vollständig genau dann, wenn:
* L in der Klasse NP liegt, das heißt $L\; \backslash in\; \{\backslash rm\; NP\}$ und
* L NP-schwierig ist, das heißt $\backslash forall\; L\text{'}\; \backslash in\; \{\backslash rm\; NP\}:\; L\text{'}\; \backslash preceq\_\{p\}\; L$.

Letztere Bedingung bedeutet, dass jedes Problem in NP durch eine Polynomialzeitreduktion auf L reduziert werden kann.

Nachweis der NP-Vollständigkeit

Der Nachweis der ersten Eigenschaft für ein gegebenes Problem ist in aller Regel einfach. Man „rät“ eine Lösung und zeigt, dass man in Polynomialzeit verifizieren kann, ob die Lösung wirklich zutrifft. Im Raten der (korrekten) Lösung findet sich der Nichtdeterminismus wieder.

Der Nachweis der zweiten Eigenschaft, die man für sich allein mit �76�NP-Schwierig�77� (oder durch falsche Rück-Übersetzung aus englisch 'NP-hard' mit NP-Hart) bezeichnet, ist schwieriger. Insbesondere bereitet es Probleme, eine Aussage für beliebige Probleme in NP zu zeigen. Daher nimmt man gewöhnlich ein ähnliches Problem, für das die NP-Vollständigkeit schon bekannt ist, und reduziert es auf dasjenige Problem, für das die Eigenschaft der NP-Schwere gezeigt werden soll. Aus der Transitivität von Polynomialzeitreduktionen folgt dann, dass alle anderen Probleme aus NP ebenfalls auf das betrachtete Problem reduzierbar sind.

Die obige Definition erfordert streng genommen einen Existenzbeweis. Es ist nicht sofort ersichtlich, dass derartige Probleme überhaupt existieren. Es lässt sich aber leicht ein solches Problem konstruieren.

Allerdings ist ein derart konstruiertes Problem kaum praxisrelevant. Cook konnte jedoch zeigen, dass das Erfüllbarkeitsproblem der Aussagenlogik NP-vollständig ist, und hat damit für ein praxisrelevantes Problem den Nachweis geführt. Dieser Beweis konnte im Gegensatz zu anderen Problemen natürlich noch nicht wie oben dargestellt über die Transitivität von Polynomialzeitreduktionen geführt werden und musste direkt erfolgen.

NP-Äquivalenz

NP-Vollständigkeit ist nur für Entscheidungsprobleme definiert, also für solche Probleme, die sich auf das Wortproblem einer formalen Sprache zurückführen lassen, für die als Antwort also nur entweder Ja oder Nein in Frage kommt. Für Optimierungsprobleme und Suchprobleme gibt es die Bezeichnung der NP-Äquivalenz.

Approximation

Probleme, die in NP liegen, lassen sich weiter in ihrer Komplexität unterteilen, je nach dem, wie gut sie sich approximativ lösen lassen. Das Graphen-Färbungsproblem ist beispielsweise nur sehr schlecht approximierbar, während sich andere Probleme beliebig gut mittels so genannter Approximationsschemata approximieren lassen.

Starke und schwache NP-Vollständigkeit

Die NP-vollständigen Probleme können weiterhin eingeteilt werden in
* stark NP-vollständige und
* schwach NP-vollständige Probleme

Ein NP-vollständiges Problem heißt stark NP-vollständig, falls es auch dann noch NP-vollständig ist, wenn die Eingabe nur aus Zahlen besteht, deren Größe im Verhältnis zur Eingabelänge polynomiell beschränkt ist. Andernfalls heißt das Problem schwach NP-vollständig. Schwache NP-Vollständigkeit bedeutet, dass für entsprechende Probleme pseudopolynomielle Algorithmen existieren können. Dies sind Algorithmen, deren Laufzeit polynomiell ist, wenn die Größe aller in der Eingabe vorkommenden Zahlen polynomiell in der Eingabelänge beschränkt ist. Für stark NP-vollständige Probleme gibt es – unter der Annahme NP ungleich P – keine derartigen Algorithmen.

Ein Beispiel für ein Problem, für das ein pseudopolynomieller Algorithmus existiert, ist das RucksackproblemSiehe Seite 73 in dem Buch "Approximationsalgorithmen eine Einführung"

von Rolf Wanka, Veröffentlicht von Vieweg+Teubner Verlag, 2006, ISBN 3519004445, ISBN 9783519004448, 206 Seiten. Durch Algorithmen, die auf dem Prinzip der dynamischen Programmierung basieren, kann eine Laufzeit, die mit O(n*V) beschränkt ist, erreicht werden. Die Rechenzeit ist somit polynomiell, falls die Zahl V (die Schranke für den maximal erlaubten Nutzwert) im Verhältnis zur Eingabelänge n nur polynomiell groß ist.

Quellen

Literatur

* Michael R. Garey und David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco 1978, ISBN 0716710455

* Stephen A. Cook: The Complexity of Theorem Proving Procedures. In Annual ACM Symposium on Theory of Computing (STOC), pp 151--158, 1971.

Weblinks

* {{Complexity Zoo|NPC (NP-Complete)|N#npc}}
* [http://www.nada.kth.se/~viggo/problemlist/compendium.html Compendium of NP-complete optimization problems] (englisch)

* [http://www.mathematik.uni-osnabrueck.de/research/OR/class/ Complexity results for scheduling Problems] (englisch)

Npvollstandigkeit

ar:مسألة NP كاملة
ca:NP-complet
cs:NP-úplnost
da:NP-komplet
NP-complete
es:NP-completo
fa:ان‌پی کامل
fi:NP-täydellisyys
Problème NP-complet
it:NP-Completo
ja:NP完全問題
ko:NP-완전
nl:NP-volledig
nn:NP-komplett
no:NP-komplett
pl:Problem NP-zupełny
pt:NP-completo
ru:NP-полная задача
simple:NP-complete
sk:NP-úplný problém
sr:НП-комплетни проблеми
sv:NP-fullständig
th:เอ็นพีบริบูรณ์
uk:NP-повна задача
vi:NP-đầy đủ
zh:NP完全

weiter