/ en / Traditional / help

Beats Biblionetz - Fragen

P=NP ?

iconBiblioMap Dies ist der Versuch, gewisse Zusammenhänge im Biblionetz graphisch darzustellen. Könnte noch besser werden, aber immerhin ein Anfang!

Diese Grafik ist nur im SVG-Format verfügbar. Dieses Format wird vom verwendeteten Browser offenbar nicht unterstützt.

Diese Grafik fensterfüllend anzeigen (SVG)

iconDefinitionen

Roger PenroseNach herrschender Expertenmeinung ist es in der Tat unmöglich, ein NP-vollständiges Problem in polynomischer Zeit mit irgendeinem Gerät vom Typ der Turing-Maschine zu lösen; demnach wären P und NP nicht dasselbe. Wahrscheinlich trifft diese Ansicht zu, aber bislang vermochte niemand sie zu beweisen. Dies bleibt das wichtigste ungelöste Problem der Komplexitätstheorie.
Von Roger Penrose im Buch Computerdenken (1989) im Text Wahrheit, Beweis und Erkenntnis auf Seite  141

iconBemerkungen

David HarelDie P=NP-Frage ist nur eine von vielen ungelösten Fragen in der Komplexitätstheorie, doch vielleicht die bedeutendste.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal können wir es nicht auf Seite  109
AlgorithmenPraktisch glaubt niemand, daß P = NP ist, und es sind beträchtliche Anstrengungen unternommen worden, um das Gegenteil zu beweisen, doch dies bleibt ein ungelöstes, offenes Problem für die Informatik.
Von Robert Sedgewick im Buch Algorithmen (1983) auf Seite  720
Peter DenningThe question of whether P = NP become the biggest open question in computing and mathematics. No one knows. That no one in any field of science, engineering, or commerce has ever found a fast algorithm for any of these 3000 problems suggests empirically that P 􀀁 NP. In our current state of knowledge all those hard problems are hard and there is little hope anyone will find a way to solve them quickly.
Von Peter Denning, Craig Martell im Text Computation (2007)
David HarelDie P=NP-Frage ist offen, seitdem sie 1971 von Cook und Levin gestellt wurde. Sie gilt als eines der schwierigsten ungelösten Probleme in der Informatik, ist aber sicherlich das faszinierendste und wichtigste. Entweder können alle diese interessanten und in Anwendungen entscheidenden Probleme gut durch Computer gelöst werden oder überhaupt keines. Außerdem braucht man nur über eines von ihnen Klarheit zu erlangen, um die ganze FrageStellung zu beenden. Außergewöhnliche Forschungsanstrengungen sind unternommen worden, um dieses Problem zu lösen, doch bislang ohne Erfolg.
Von David Harel im Buch Das Affenpuzzle (2000) im Text Manchmal wissen wir es nicht auf Seite  106

iconEinträge in Beats Blog

iconZitationsgraph

Diese Grafik ist nur im SVG-Format verfügbar. Dieses Format wird vom verwendeteten Browser offenbar nicht unterstützt.

Diese Grafik fensterfüllend anzeigen (SVG)

iconZeitleiste

icon12 Erwähnungen  Dies ist eine nach Erscheinungsjahr geordnete Liste aller im Biblionetz vorhandenen Werke, die das ausgewählte Thema behandeln.

iconExterne Links

Auf dem WWW P vs NP Problem: Clay Mathemtatics Institute "Millenium Problems" ( WWW: Link tot Link unterbrochen? Letzte Überprüfung: 2020-11-28 Letzte erfolgreiche Überprüfung: 2013-11-28)

iconAnderswo suchen  Auch im Biblionetz finden Sie nicht alles. Aus diesem Grund bietet das Biblionetz bereits ausgefüllte Suchformulare für verschiedene Suchdienste an. Biblionetztreffer werden dabei ausgeschlossen.

iconBiblionetz-History Dies ist eine graphische Darstellung, wann wie viele Verweise von und zu diesem Objekt ins Biblionetz eingetragen wurden und wie oft die Seite abgerufen wurde.