NP-Vollständig

In der Informatik bezeichnet man ein Problem als NP-vollständig (vollständig für die Klasse der Probleme, die sich nichtdeterministisch in Polynomialzeit lösen lassen), wenn es zu den schwierigsten Problemen in der Klasse NP gehört, also sowohl in NP liegt, als auch NP-schwer ist. Dies bedeutet umgangssprachlich, dass es sich vermutlich nicht effizient lösen lässt.