NP-schwere Probleme

Definition

Eine Sprache $L$ heißt NP-schwer, wenn für alle $L^{\prime }\in NP$ gilt $L^{\prime }{\le }_{p}L$
Für jede NP-schwere Sprache $L$ gilt: wenn $L\in P$, dann P = NP

Ist P-Time = NP-Time ???

Polynomialzeitreduktionen
NP-vollständig