NP-schwer

Eine Sprache $A$ heißt NP-schwer (NP-hard), wenn alle Sprachen aus NP polynomiell auf $A$ reduzierbar sind:

\forall L \in N P : L \leq_{m}^{p} A

Ein NP-schweres Problem muss selbst nicht in NP liegen.