/ en / Traditional / help

Beats Biblionetz - Begriffe

Komplexitätstheorie

Diese Seite wurde seit 3 Jahren inhaltlich nicht mehr aktualisiert. Unter Umständen ist sie nicht mehr aktuell.

iconDefinitionen

Roger PenroseWie sich zeigt, gibt es selbst unter denjenigen mathematischen Problemen, die ihrem Wesen nach algorithmisch sind, einige Klassen von Problemen, die wegen ihrer Eigenart um vieles schwieriger algorithmisch lösbar sind als andere. Die schwierigen lassen sich nur durch sehr langsame Algorithmen lösen (oder vielleicht mit Algorithmen, die unverhältnismäßig viel Speicherplatz erfordern, und so weiter). Mit derartigen Fragen befaßt sich die sogenannte Komplexitätstheorie.
Von Roger Penrose im Buch Computerdenken (1989) im Text Wahrheit, Beweis und Erkenntnis auf Seite  137

iconBemerkungen

Roger PenroseDie Komplexitätstheorie beschäftigt sich nicht so sehr mit der Schwierigkeit, einzelne Probleme algorithmisch zu lösen, sondern mit unendlichen Problemfamilien, wobei es einen allgemeinen Algorithmus zum Auffinden von Lösungen für sämtliche Probleme einer einzelnen Familie geben soll.
Von Roger Penrose im Buch Computerdenken (1989) im Text Wahrheit, Beweis und Erkenntnis auf Seite  137
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

iconVerwandte Objeke

icon
Verwandte Begriffe
(co-word occurance)
NP(0.06), NP-completeNP-complete(0.05), BerechenbarkeitComputability(0.03), P (PTIME)(0.03), divide and conquerdivide and conquer(0.03)

iconHäufig co-zitierte Personen

Otto E. Rössler Otto E.
Rössler
Donald E. Knuth Donald E.
Knuth
Gunter Dueck Gunter
Dueck
David Hilbert David
Hilbert
Frege Frege
Kurt Gödel Kurt
Gödel

iconStatistisches Begriffsnetz  Dies ist eine graphische Darstellung derjenigen Begriffe, die häufig gleichzeitig mit dem Hauptbegriff erwähnt werden (Cozitation).

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

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

iconAnderswo finden

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.