/ en / Traditional / mobile

Beats Biblionetz - Begriffe

Komplexitätstheorie

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
(Cozitation)
NP-completeNP-complete, NP, BerechenbarkeitComputability, Turing-Maschineturing machine, P (PTIME)

iconHäufig co-zitierte Personen

Otto E. Rössler Otto E.
Rössler
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).

Diese Grafik fensterfüllend anzeigen als Pixelgrafik (PNG) Vektorgrafik (SVG)

iconZitationsgraph

Diese Grafik fensterfüllend anzeigen als Pixelgrafik (PNG) Vektorgrafik (SVG)

iconErwä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.

Verweise auf Komplexitätstheorie 1532276226123522
Webzugriffe auf Komplexitätstheorie 
2002200320042005200620072008200920102011201220132014201520162017