Online-Bibliothek

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 makroskopische Dimensionen wächst.

Formal ist ein Suchproblem NP-äquivalent, wenn es NP-leicht und NP-schwer ist. Dies ist genau dann der Fall, wenn das zugehörige Entscheidungsproblem NP-vollständig ist. Ein NP-äquivalentes Problem ist genau dann in polynomieller Zeit lösbar, wenn P=NP ist.