NP-schwere Probleme

NP-schwere Probleme

Für NP-schwere Probleme gilt, dass Probleme aus der Komplexitätsklasse NP in polynomieller Zeit auf diese reduzieren lassen. Dabei gilt, dass NP-schwere Probleme mindestens so ”schwer” wie Probleme aus NP sind. NP-schwere Probleme liegen also entweder in NP oder in einer höheren Komplexitätsklasse.