Basiswissen

Die Komplexitätstheorie, kurz auch KT^[1] beschäftigt sich mit der Komplexität algorithmisch behandelbarer Probleme. Als Komplexität wird dabei das Maß des irgendwie gemessene^[6] mindestens nötige Ressourcenverbrauch von Rechnern verstanden^[7].

Ziele der Komplexitätstheorie

Emergenz von Ordnung verstehen^[1]

Klassifzierung von Problemen nach algorithmischen Aufwand^[7]

Abgrenzung zur Berechenbarkeitstheorie

Geht es nicht um die Frage, mit welchem algorithmischen Aufwand ein Problem lösbar ist, sondern ob es überhaupt mit einem Algorithmus lösbar, bewegt man sich innerhalb der sogenannten Berechenbarkeitstheorie. Siehe dazu auch den Artikel zur Berechenbarkeit ↗

Fußnoten

[1] "Ziel der Komplexitätstheorie (KT) ist es, die allgemeinen Gesetze der Emergenz von Ordnungszuständen in komplexen Systemen auf einer abstrakten Modellebene zu verstehen und dann auf die unterschiedlichsten substanzwissenschaftlichen Anwendungsbereiche zu übertragen." In:

[2] Peter Kappelhoff: Chaos- und Komplexitätstheorie. Februar 2003.

[3] Peter Kappelhoff: Komplexitätstheorie: Neues Paradigma für die Managementforschung? In: Managementforschung 12 (hrsg. von Schreyögg, G./Conrad, P.). 2002. S. 49-101.

[4] Stuart Kauffman: Der Öltropfen im Wasser. Chaos, Komplexität, Selbstorganisation in Natur und Gesellschaft. Piper Verlag. München. 1996.

[5] Peter Kappelhoff. Die evolutionäre Organisationstheorie im Lichte der Komplexitätstheorie. 2007.

[6] "Die Komplexitätstheorie als Teilgebiet der theoretischen Informatik befasst sich mit der Komplexität algorithmisch behandelbarer Probleme auf verschiedenen formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf, manchmal auch speziellere Maße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen." In: der Artikel "Komplexitätstheorie". Wikipedia. Abgerufen am 5. August 2024. Online: https://de.wikipedia.org/wiki/Komplexitätstheorie

[7] "Die Komplexität eines Problems ist [...] die Komplexität desjenigen Algorithmus, der das Problem mit dem geringstmöglichen Ressourcenverbrauch löst." In: der Artikel "Komplexitätstheorie". Wikipedia. Abgerufen am 5. August 2024. Online: https://de.wikipedia.org/wiki/Komplexitätstheorie

[8] "[…] das wichtigste Forschungsziel der Komplexitätstheorie [besteht] darin, die Menge aller lösbaren Probleme zu klassifizieren." In: der Artikel "Komplexitätstheorie". Wikipedia. Abgerufen am 5. August 2024. Online: https://de.wikipedia.org/wiki/Komplexitätstheorie

[9] "Die Berechenbarkeitstheorie (auch Rekursionstheorie) ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik, die sich mit dem Begriff der Berechenbarkeit befasst, insbesondere damit, welche Probleme mit Hilfe einer Maschine (genauer: eines mathematischen Modells einer Maschine) oder eines anderen mathematischen Modells der Berechenbarkeit lösbar sind." In: