Ein Problem ist NP-schwer, wenn jedes Problem aus NPNPNP in polynomieller Zeit darauf reduzierbar ist.
Es muss selbst nicht in NPNPNP liegen und nicht einmal ein Entscheidungsproblem sein.