NP

Diese Seite wurde seit mehr als 7 Monaten inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

Definitions

Bücher first.

Menge aller Probleme, die mit Hilfe nichtdeterministischer Algorithmen in polynomialer Zeit gelöst werden können.

From Robert Sedgewick im Buch Algorithmen (1983) on page 719

Klasse von Problemen,die von nichtdeterministischen (=optimal ratendem) Algorithmen in polynomialer Zeit gelöst werden können.

From Beat Döbeli Honegger, saved in Beats Biblionetz on 28.12.2002

NP (ohne "-vollständig") steht für die Klasse der Probleme, für die es magische, nicht-deterministische Polynomialzeit-Algorithmen gibt.

From David Harel im Buch Das Affenpuzzle (2000) in the text Manchmal wissen wir es nicht on page 106

Similar Objects

Related Concepts (co-word occurance)	NP-complete NP-complete(0.66), P (PTIME)(0.27), Knapsack-Problem Knapsack-Problem(0.11), Komplexitätstheorie(0.06), Traveling Salesman Problem Traveling Salesman Problem(0.05)
Related Questions	P=NP ?

Statistical Concept Network

Diese interaktive Grafik in neuem Fenster öffnen

Citation Graph

Diese SVG-Grafik fensterfüllend anzeigen

Citation Graph(Beta-Test mit vis.js)

Diese interaktive Grafik in neuem Fenster öffnen (mit mehr Interaktionsmöglichkeiten)

Timeline

Diese interaktive Grafik in neuem Fenster öffnen

15 References

Algorithmen (Robert Sedgewick) (1983)
Das Affenpuzzle - und weitere bad news aus der Computerwelt (David Harel) (2000)
- 3. Manchmal ist es zu teuer
- 4. Manchmal wissen wir es nicht
Abenteuer Internet - Lernen mit WebQuests (Heinz Moser) (2000)
- 3. Ich packe meinen Koffer und ... (Jens Gallenbacher)
Studium generale zur Komplexität (Hans Diebner) (2001)
- 8. Realität, Aktualität, Ästhetik und Interpretation (Hans Diebner, Peter Weibel)
The New Turing Omnibus (A. K. Dewdney) (2001)
- 41. NP-Vollständigkeit
- 54. NP-vollständige Probleme
A New Kind of Science (Stephen Wolfram) (2002)
- 10. Processes of Perception and Analysis
- 12. The Principle of Computational Equivalence
GraphBench - Exploring the Limits of Complexity with Educational Software (ETH Dissertation 16392) (Markus Brändle) (2006)
LOG IN 148/2007 (2007)
- Das Knotenüberdeckungsproblem - Eine Fallstudie zur Didaktik NP-schwerer Probleme (Teil 2) (Rolf Niedermeier, Jörg Vogel, Michael Fothe, Mirko König) (2007)
LOG IN 146/147/2007 - Informatische Kompetenzen - Bildungsstandards (2007)
- Das Knotenüberdeckungsproblem - Eine Fallstudie zur Didaktik NP-schwerer Probleme (Teil 1) (Rolf Niedermeier, Jörg Vogel, Michael Fothe, Mirko König) (2007)
Computation - A New way of science (Peter Denning, Craig Martell) (2007)
Gleichzeitige Ungleichzeitigkeiten - Eine Einführung in die Komplexitätsforschung (Manfred Füllsack) (2011)
- 1. Entwicklungen
The Master Algorithm - How the Quest for the Ultimate Learning Machine Will Remake Our World (Pedro Domingos) (2015)
- 2. The Master Algorithm