Vollständigkeit (Komplexitätstheorie)

In der theoretischen Informatik - insbesondere in der Berechenbarkeits- und der Komplexitätstheorie - bezeichnet die Schwere (nach einer Fehlübersetzung von engl. hardness auch Härte) eines Problems dessen Eigenschaft, mindestens so schwierig lösbar zu sein wie alle Probleme einer betrachteten Klasse. Die Vollständigkeit eines Problems bedeutet dann, dass es sich um ein schwierigstes Problem aus dieser Klasse handelt. Anschaulich gesprochen kann also ein Algorithmus, der ein schweres Problem lösen kann, mit nur geringen Modifikationen auch alle Probleme der entsprechenden Klasse lösen.