NP-Äquivalenz

Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 1. Februar 2005 um 18:17 Uhr durch 139.30.18.129 (Diskussion). Sie kann sich erheblich von der aktuellen Version unterscheiden.

(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

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.

Abgerufen von „https://de.wikipedia.org/w/index.php?title=NP-Äquivalenz&oldid=4324382“