In der Informatik bezeichnet man ein Problem als NP-vollstandig ( vollstandig fur die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit losen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehort, also sowohl in NP liegt als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient losen lasst.

Formal wird NP-Vollstandigkeit nur fur Entscheidungsprobleme definiert (mogliche Losungen nur ?ja“ oder ?nein“), wahrend man bei anderen Problemtypen von NP-Aquivalenz spricht (etwa bei Suchproblemen oder Optimierungsproblemen ). Umgangssprachlich wird diese Unterscheidung jedoch oft nicht vollzogen, so dass man ganz allgemein von ?NP-vollstandigen Problemen“ spricht, unabhangig davon, ob ein Entscheidungsproblem vorliegt oder nicht. Dies ist moglich, da verschiedene Problemtypen ineinander uberfuhrbar (aufeinander reduzierbar) sind.

Ein Entscheidungsproblem ist NP-vollstandig, wenn es

• in der Komplexitatsklasse NP liegt: Ein deterministisch arbeitender Rechner benotigt nur polynomiell viel Zeit, um zu entscheiden, ob eine vorgeschlagene Losung eines zugehorigen Suchproblems tatsachlich eine Losung ist, und
• zu den NP-schweren Problemen gehort: Alle anderen Probleme, deren Losungen deterministisch in polynomieller Zeit uberpruft werden konnen, konnen auf das Problem derart zuruckgefuhrt werden, dass diese Ruckfuhrung auf einem deterministischen Rechner hochstens polynomielle Zeit in Anspruch nimmt. Man spricht von einer Polynomialzeitreduktion .

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

NP-vollstandige Probleme lassen sich vermutlich nicht effizient losen, da ihre Losung 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 fur viele NP-vollstandige Probleme Losungsverfahren, anhand deren sie fur in der Praxis auftretende Großenordnungen in akzeptabler Zeit losbar sind.

Viele in der Praxis auftauchende und wichtige Probleme sind NP-vollstandig, was NP-Vollstandigkeit zu einem zentralen Begriff der Informatik macht. Weiter verstarkt wird diese Bedeutung durch das sogenannte P-NP-Problem :

1. Fur kein NP-vollstandiges Problem konnte bisher nachgewiesen werden, dass es in polynomieller Zeit losbar ware.
2. Falls nur ein einziges dieser Probleme in polynomieller Zeit losbar ware, dann ware jedes Problem in NP in polynomieller Zeit losbar, was große Bedeutung fur die Praxis haben konnte (jedoch nicht notwendigerweise haben muss).

Seit der Einfuhrung der NP-Vollstandigkeit durch Cook wurde die Vollstandigkeit zu einem allgemeinen Konzept fur beliebige Komplexitatsklassen ausgebaut.

Geschichte [ Bearbeiten | Quelltext bearbeiten ]

Der Begriff der NP-Vollstandigkeit wurde 1971 von Stephen A. Cook in seinem heute so genannten Satz von Cook eingefuhrt. Darin zeigte er, dass das Erfullbarkeitsproblem der Aussagenlogik NP-vollstandig ist. Heute existieren deutlich einfachere konstruktive Nachweise fur die Existenz solcher Probleme, allerdings sind die dafur verwendeten Sprachen sehr kunstlich. Cooks Verdienst besteht also auch darin, fur 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-Vollstandigkeit zu noch großerer Popularitat verhalf. Karps Verdienst besteht darin, die Technik der Polynomialzeitreduktion konsequent genutzt zu haben, um fur weitere 21 populare Probleme die NP-Vollstandigkeit nachzuweisen.

Definition [ Bearbeiten | Quelltext bearbeiten ]

Ein Problem (genauer: ein Entscheidungsproblem ) L heißt NP-vollstandig genau dann, wenn:

• L in der Klasse NP liegt, das heißt ${\displaystyle L\in {\rm {NP}}}$ und
• L NP-schwer ist, das heißt ${\displaystyle \forall L'\in {\rm {NP}}:L'\preceq _{p}L}$.

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

Nachweis der NP-Vollstandigkeit [ Bearbeiten | Quelltext bearbeiten ]

Der Nachweis der ersten Eigenschaft fur ein gegebenes Problem ist in aller Regel einfach. Man ?rat“ eine Losung und zeigt, dass man in Polynomialzeit verifizieren kann, ob die Losung wirklich zutrifft. Im Raten der (korrekten) Losung findet sich der Nichtdeterminismus wieder.

Der Nachweis der zweiten Eigenschaft, die man fur sich allein mit NP-schwer (oder durch falsche Ruckubersetzung aus englisch 'NP-hard' mit NP-hart ) bezeichnet, ist schwieriger, insbesondere wenn es darum geht, eine Aussage fur beliebige Probleme in NP zu zeigen. Daher nimmt man gewohnlich ein ahnliches Problem, fur das die NP-Vollstandigkeit schon bekannt ist, und reduziert es auf dasjenige Problem, fur das die Eigenschaft der NP-Schwere gezeigt werden soll. Aus der Transitivitat 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 uberhaupt existieren. Es lasst sich aber leicht ein solches Problem konstruieren. Allerdings ist ein derart konstruiertes Problem kaum praxisrelevant. Cook konnte jedoch zeigen, dass das Erfullbarkeitsproblem der Aussagenlogik NP-vollstandig ist, und hat damit fur ein praxisrelevantes Problem den Nachweis gefuhrt. Dieser Beweis konnte im Gegensatz zu anderen Problemen naturlich noch nicht wie oben dargestellt uber die Transitivitat von Polynomialzeitreduktionen gefuhrt werden und musste direkt erfolgen.

NP-Aquivalenz [ Bearbeiten | Quelltext bearbeiten ]

NP-Vollstandigkeit ist nur fur Entscheidungsprobleme definiert, also fur solche Probleme, die sich auf das Wortproblem einer formalen Sprache zuruckfuhren lassen, fur die als Antwort also nur entweder Ja oder Nein in Frage kommt. Fur Optimierungsprobleme und Suchprobleme gibt es die Bezeichnung der NP-Aquivalenz .

Approximation [ Bearbeiten | Quelltext bearbeiten ]

Probleme, die in NP liegen, lassen sich weiter in ihrer Komplexitat unterteilen, je nachdem, wie gut sie sich approximativ losen lassen. Das Graphen-Farbungsproblem ist beispielsweise nur sehr schlecht approximierbar, wahrend sich andere Probleme beliebig gut mittels so genannter Approximationsschemata approximieren lassen.

Starke NP-Vollstandigkeit [ Bearbeiten | Quelltext bearbeiten ]

Ein NP-vollstandiges Problem heißt stark NP-vollstandig , falls es auch dann noch NP-vollstandig ist, wenn man es auf solche Eingabeinstanzen beschrankt, die nur solche Zahlen (als numerische Parameter) enthalten, deren Große im Verhaltnis zur Eingabelange polynomiell beschrankt ist (solch ein Problem ist stets wieder in NP). Oder anders ausgedruckt: Wenn man das Problem so modifiziert, dass alle numerischen Parameter im Unarsystem in der Eingabe stehen, bleibt es NP-vollstandig. Fur stark NP-vollstandige Probleme gibt es unter der Annahme NP ungleich P keine pseudopolynomiellen Algorithmen. Dies sind Algorithmen, deren Laufzeit polynomiell ist, wenn die Große aller in der Eingabe vorkommenden Zahlen polynomiell in der Eingabelange beschrankt ist.

Ein Beispiel fur ein Problem, fur das ein pseudopolynomieller Algorithmus existiert, ist das Rucksackproblem . Durch Algorithmen, die auf dem Prinzip der dynamischen Programmierung basieren, kann eine Laufzeit, die mit ${\displaystyle {\mathcal {O}}(n^{2}\cdot V)}$ beschrankt ist, erreicht werden. Die Rechenzeit ist somit polynomiell, falls die Zahl ${\displaystyle V}$ (die Schranke fur den maximal erlaubten Nutzwert) im Verhaltnis zur Eingabelange ${\displaystyle n}$ nur polynomiell groß ist. ^[1] Solche NP-vollstandigen Probleme, mit einem pseudopolynomiellen Algorithmus, werden auch schwach NP-vollstandig genannt. ^[2]

Quellen [ Bearbeiten | Quelltext bearbeiten ]

1. ↑ Siehe Seite 157 in dem Buch "Algorithmics for hard problems: introduction to combinatorial optimization, randomization, approximation, and heuristics" von Juraj Hromkovi?, Veroffentlicht von Springer Verlag, 2001, ISBN 3519004445 , ISBN 9783540668602 .
2. ↑ Leslie Hall: Computational Complexity. Abgerufen am 10. Dezember 2012 .  

Literatur [ Bearbeiten | Quelltext bearbeiten ]

• 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 [ Bearbeiten | Quelltext bearbeiten ]

• NPC (NP-Complete) . In: Complexity Zoo. (englisch)
• Compendium of NP optimization problems (englisch)
• Complexity results for scheduling Problems (englisch)