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 makrokosmische 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.

Literatur

• Michael Garey, David Stifler Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness, S. 117, 120. W. H. Freeman and Company, New York, 1979.