Psychologie Lexikon der Argumente

Home Screenshot Tabelle Begriffe

 
NP-Vollständigkeit: NP-Vollständigkeit ist ein Begriff aus der Komplexitätstheorie. Ein Problem ist NP-vollständig, wenn es sowohl in NP ist (was bedeutet, dass es in polynomialer Zeit von einer nicht-deterministischen Turing-Maschine gelöst werden kann) als auch NP-hart (was bedeutet, dass jedes andere Problem in NP in polynomialer Zeit darauf reduziert werden kann). Siehe auch Berechenbarkeit, Komplexität, Reduzierbarkeit, Turing-Maschine.

_____________
Anmerkung: Die obigen Begriffscharakterisierungen verstehen sich weder als Definitionen noch als erschöpfende Problemdarstellungen. Sie sollen lediglich den Zugang zu den unten angefügten Quellen erleichtern. - Lexikon der Argumente.

 
Autor Begriff Zusammenfassung/Zitate Quellen

Peter Norvig über NP-Vollständigkeit – Lexikon der Argumente

Norvig I 8
NP-Vollständigkeit/Russell/Norvig: Wie kann man ein unlösbares Problem erkennen? Die Theorie der NP-Vollkommenheit, die von Steven Cook (1971)(1) und Richard Karp (1972(2)) entwickelt wurde, bietet eine Methode. Cook und Karp zeigten die Existenz großer Klassen von kanonischen kombinatorischen Such- und Argumentationsproblemen, die NP-vollständig sind. Jede Problemklasse, auf die die Klasse der NP-vollständigen Probleme reduziert werden kann, ist wahrscheinlich unlösbar. (Obwohl nicht nachgewiesen wurde, dass NP-vollständige
Norvig I 9
Probleme notwendigerweise unlösbar sind, glauben die meisten Theoretiker es.) Diese Ergebnisse stehen im Gegensatz zu dem Optimismus, mit dem die Boulevardpresse die ersten Computer begrüßte (...).


1. Cook, S. A. (1971). The complexity of theorem proving procedures. In STOC-71, pp. 151–158.
2. Karp, R. M. (1972). Reducibility among combinatorial problems. In Miller, R. E. and Thatcher, J. W.
(Eds.), Complexity of Computer Computations, pp. 85–103. Plenum.


_____________
Zeichenerklärung: Römische Ziffern geben die Quelle an, arabische Ziffern die Seitenzahl. Die entsprechenden Titel sind rechts unter Metadaten angegeben. ((s)…): Kommentar des Einsenders. Übersetzungen: Lexikon der Argumente
Der Hinweis [Begriff/Autor], [Autor1]Vs[Autor2] bzw. [Autor]Vs[Begriff] bzw. "Problem:"/"Lösung", "alt:"/"neu:" und "These:" ist eine Hinzufügung des Lexikons der Argumente.

Norvig I
Peter Norvig
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010

Send Link

Autoren A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z  


Begriffe A   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   Z