Wikipedia

NP-Vollständigkeit

Begriff aus der Informatik
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 21. Juli 2003 um 21:45 Uhr durch 62.72.92.90 (Diskussion). Sie kann sich erheblich von der aktuellen Version unterscheiden.
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)

NP-Vollständigkeit

Ein Problem L heisst NP-vollständig, wenn es eine Polynomialzeitreduktion aller Probleme in P auf L gibt.

Dies wird natürlich nicht so häufig f¨r konkrete Probleme gezeigt, weil es recht schwierig ist eine Aussage für beliebige Probleme in P zu zeigen. Vielmehr nimmt man ein Problem, f ür das die NP-Vollständigkeit schon bekannt ist und reduziert es auf dasjenige Problem, für das man die Eigenschaft der NP-Vollständigkeit zeigen will.

Abgerufen von „https://de.wikipedia.org/w/index.php?title=NP-Vollständigkeit&oldid=212933“