NP-Vollständigkeit

Ein Problem (genauer: ein Entscheidungsproblem) L heißt NP-vollständig, gdw

L ∈ NP
Es gibt eine Polynomialzeitreduktion aller Probleme in NP auf L

Genau so wird dies natürlich nicht so häufig für konkrete Probleme gezeigt, weil es recht schwierig ist, eine Aussage für beliebige Probleme in NP zu zeigen. Vielmehr nimmt man ein Problem, für das die NP-Vollständigkeit schon bekannt ist und reduziert es auf dasjenige Problem, für das man die Eigenschaft der NP-Vollständigkeit zeigen will. Aus der Transitivität von Polynomialzeitreduktionen folgt dann, dass alle Probleme aus NP auch auf das betrachtete Problem reduzierbar sind.

Klassische Vertreter NP-vollständiger Probleme sind etwa

SAT
3-SAT
Vertex Cover
das Bin Packing Problem
das Rucksackproblem (auch bekannt als Knap Sack Problem)
...

Erstaunlicherweise lassen sich diese schweren Probleme der Informatik zwar wahrscheinlich (unter der Annahme, dass P≠NP gilt) nicht im Allgemeinen lösen, jedoch in einigen Fällen beliebig genau mit sogenannten Approximationsschemata approximieren.

NP-Schwere (NP-Härte)

Ein verwandter Begriff zur NP-Vollständigkeit ist die NP-Schwere (oft auch als "NP-Härte" bezeichnet - aus dem englischen zurückübersetzt). Der Begriff NP-Vollständigkeit bezieht sich nur auf Probleme aus NP (also Entscheidungsprobleme). Ein Problem heißt dann NP-schwer, wenn die Bedingungen von oben erfüllt sind, das Problem jedoch nicht in NP liegt.

starke und schwache NP-Vollständigkeit

Weiter kann man die NP-vollständigen Probleme noch einteilen in

stark NP-vollständige und
schwach NP-vollständige Probleme

Bleibt das Problem auch noch mit unärer Kodierung der Eingabe NP-vollständig, so heißt das Problem stark NP-vollständig, ansonsten schwach NP-vollständig. Eine alternative Definition besagt, dass es für schwach NP-vollständige Probleme sogenannte pseudopolynomielle Algorithmen gibt, für stark NP-vollständige Probleme dagegen nicht. Algorithmen, bei denen in der Laufzeitschranke eine Zahl vorkommt, die nicht polynomiell von der Eingabelänge abhängt, nennt man pseudopolynomiell, da die Laufzeit nicht zwangsläufig polynomiell sein muss - etwa, wenn diese Zahl so groß wird, dass sie exponentiell in der Eingabelänge ist.