NP-Vollständig

Ein Problem $L\in NP$ heißt NP-vollständig, wenn:

1. $L\in NP$
2. Für jedes Problem $B\in NP$ existiert eine polynomielle Reduktion $$B \le_p L.$$ bzw. ist NP-schwer

Das bedeutet:
Wenn man ein NP-vollständiges Problem in Polynomialzeit lösen könnte,
dann auch alle Probleme in NP — also wäre $P=NP$.