Komplexitätstheorie

Die Komplexitätstheorie als Teilgebiet der Theoretischen Informatik befasst sich mit der Komplexität von algorithmisch behandelbaren Problemen auf verschiedenen mathematisch definierten formalen Rechnermodellen. Die Komplexität von Algorithmen wird in deren Ressourcenverbrauch gemessen, meist Rechenzeit oder Speicherplatzbedarf. Es werden jedoch auch speziellere Komplexitätsmaße wie die Größe eines Schaltkreises oder die Anzahl benötigter Prozessoren bei parallelen Algorithmen untersucht.

Die Komplexitätstheorie unterscheidet sich von der Berechenbarkeitstheorie, die sich mit der Frage beschäftigt, welche Probleme prinzipiell algorithmisch gelöst werden können. Demgegenüber besteht das wichtigste Forschungsziel der Komplexitätstheorie darin, die Menge aller lösbaren Probleme zu klassifizieren. Insbesondere versucht man, die Menge der effizient lösbaren Probleme von der Menge der inhärent schwierigen Probleme abzugrenzen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Komplexitätstheorie aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung