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

1. 
2. Es gibt eine Polynomialzeitreduktion aller Probleme in NP auf L (vgl. NP-Schwere)

Exakt 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 das Merkmal 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.

Probleme heissen auch NP-hart, wenn sie auf NP-Vollständige Probleme reduzierbar sind, aber selbst in P liegen.

Klassische Vertreter NP-vollständiger Probleme sind etwa

• Erfüllbarkeitsproblem der Aussagenlogik (SAT)
• 3-SAT
• Max2SAT
• Vertex Cover
• Clique
• Partition
• gerichteter bzw. ungerichteter Hamiltonkreis
• Problem des Handlungsreisenden (traveling salesman problem)
• das Bin-Packing-Problem
• das Rucksackproblem (Knap-Sack-Problem)
• 3COLOR
• Exact Cover
• Subset Sum
• ...

Der Begriff NP-Vollständigkeit ist ca. für Entscheidungsprobleme definiert, also solche Probleme, die sich auf das Wortproblem einer formalen Sprache zurückführen lassen. Für Optimierungsprobleme und Suchprobleme gibt es den Begriff der NP-Äquivalenz .

Probleme die in NP liegen, lassen sich weiter in ihrer Komplexität unterteilen, je nachdem, wie gut sie sich approximativ lösen lassen. Das Graphen-Färbungsproblem läßt sich beispielsweise ca. sehr schlecht approximativ lösen, während andere Probleme beliebig gut mittels so genannten Approximationsschemata approximieren lassen.

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

• stark NP-vollständige und
• schwach NP-vollständige ProblemeBleibt 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 so genannte 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, bezeichnet 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.== Lösungsansätze ==

Probleme dieser Problemklasse haben die unangenehmes Merkmal, dass die Rechenzeit bei zunehmender Datenmenge rasch in das astronomische steigt. Eine vollständige und optimale Lösung ist daher bestenfalls für kleine Datenmengen zu erreichen. In dem Rahmen der Software-Entwicklung folgt man drei Lösungsansätzen, um ein solches Problem anzuprogrammieren:

1. Man schreibt tatsächlich einen optimalen Algorithmus, geht jedoch davon aus, dass die zu verarbeitende Datenmenge immer in einem Bereich bleibt, der klein genug ist, um die Lösung abzuwarten.
2. Man wählt einen heuristischen Algorithmus, also ein regelbasiertes System und sucht nicht nach einer optimalen Lösung, sondern ca. nach einer Lösung, die für die konkrete Aufgabe gut genug ist.
3. Man wählt einen approximativen Algorithmus, der nicht die perfekte Lösung, aber eine nahezu perfekte Lösung bietet.

Siehe auch: NP (Komplexitätsklasse), Komplexitätsklasse