In der Informatik bezeichnet man ein Problem als NP-vollständig (nichtdeterministisch polynomielle Vollständigkeit), wenn Der erste der beiden Punkte drückt aus, dass das Problem in der Komplexitätsklasse NP liegt. Durch diese Definition wird auch die Klasse NP-C der NP-vollständigen Probleme definiert. Die Eigenschaften dieser und anderer Kl...