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.

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

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

starke und schwache NP-Vollständigkeit

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.