Bewertung:
In den Rezensionen wird „The Golden Ticket“ von Fortnow als wertvolle Einführung in das P-gegen-NP-Problem hervorgehoben, die ein ausgewogenes Verhältnis zwischen Zugänglichkeit und Tiefe bietet. Viele Leser schätzen den fesselnden Schreibstil, die Anekdoten und die klaren Erklärungen, die komplexe Themen auch für Laien verständlich machen. Einige Leser haben jedoch Schwierigkeiten mit den technischen Notationen und können ihnen nur schwer folgen, was darauf hindeutet, dass Vorkenntnisse oder ein grundlegendes Verständnis erforderlich sind.
Vorteile:⬤ Fesselnder und gut lesbarer Schreibstil
⬤ klare Erklärungen komplexer Themen
⬤ enthält Anekdoten und Diagramme
⬤ umfassende Behandlung von P vs. NP und verwandten Themen
⬤ gilt als sanfte Einführung in ein schwieriges Thema.
⬤ Verwendet Notationen, die nicht erklärt werden, was es einigen Lesern schwer macht, dem Buch zu folgen
⬤ erfordert Vorkenntnisse für ein vollständiges Verständnis
⬤ könnte für fortgeschrittene Leser zu vereinfacht sein.
(basierend auf 2 Leserbewertungen)
P, Np, and Np-Completeness: The Basics of Computational Complexity
Der Schwerpunkt dieses Buches liegt auf der P-versus-NP-Frage und der Theorie der NP-Vollständigkeit. Es bietet auch angemessene Vorarbeiten zu Berechnungsproblemen und Berechnungsmodellen.
Die P-versus-NP-Frage fragt, ob es schwieriger ist, Lösungen zu finden als die Korrektheit von Lösungen zu überprüfen. Eine alternative Formulierung fragt, ob die Entdeckung von Beweisen schwieriger ist als die Überprüfung ihrer Korrektheit. Es wird allgemein angenommen, dass die Antwort auf diese äquivalenten Formulierungen positiv ist, und dies wird durch die Aussage erfasst, dass P sich von NP unterscheidet.
Obwohl die P-versus-NP-Frage nach wie vor ungelöst ist, bietet die Theorie der NP-Vollständigkeit Beweise für die Unlösbarkeit bestimmter Probleme in NP, indem sie zeigt, dass sie für die gesamte Klasse universell sind. Erstaunlicherweise gibt es NP-komplette Probleme, und darüber hinaus sind Hunderte von natürlichen Rechenproblemen, die in vielen verschiedenen Bereichen der Mathematik und Wissenschaft auftreten, NP-komplett.
| ISBN: | 9780521122542 |
| Autor: | |
| Verlag: | |
| Sprache: | Englisch |
| Einband: | Taschenbuch |
| Erscheinungsjahr: | 2010 |
| Seitenzahl: | 216 |
Derzeit verfügbar, auf Lager.
