NP-Vollständigkeit

Ein Problem (genauer: ein Entscheidungsproblem) L heisst NP-vollständig, wenn es eine Polynomialzeitreduktion aller Probleme in P auf L gibt.

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 P 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 P 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-Härte

Ein verwandter Begriff zur NP-Vollständigkeit ist die NP-Schwere (oft auch als "NP-Härte" aus dem englischen zurückübersetzt). Der Begriff NP-Vollständigkeit bezieht sich nur auf Probleme aus NP (also Entscheidungsprobleme). Ein Problem heisst 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 heisst das Problem stark NP-vollständig, ansonsten schwach NP-vollständig.