NP-Vollständigkeit
Ein Problem L heisst NP-vollständig, wenn das Problem mit polynominaler Rechenzeit lösbar ist, d.h. die Rechenzeit wächst mit einer Polynomialfunktion der Anzahl Elemente N und nicht mit einer Exponentialfunktion. (N kommt nicht im Exponenten vor).
Dies wird 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.
Weiter kann man die NP-vollständigen Probleme noch einteilen in
- stark NP-vollständige und
- schwach NP-vollständige Probleme