NP-Äquivalenz
NP-Äquivalenz ist ein Begriff aus der Komplexitätstheorie innerhalb der Informatik. Es liefert eine prinzipielle Aussage darüber, ob Suchprobleme mit wachsender Anzahl der zu durchsuchenden Pfade oder Objekte noch praktisch lösbar sind, oder ob der benötigte Zeit- oder Speicheraufwand rasch in astronomische Dimensionen wächst.
Die formale Definition des Begriffs lautet:
Ein Suchproblem heißt NP-äquivalent, wenn es NP-leicht und NP-schwer ist. Ein NP-äquivalentes Problem ist genau dann in polynomieller Zeit lösbar, wenn P=NP ist.
Siehe auch: NP-Vollständigkeit