Philosophie Lexikon der ArgumenteHome | |||
| |||
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 ArgumenteDer 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 |