Komplexitätstheorie

Quelle: Wikipedia. Seiten: 73. Kapitel: Turingmaschine, Knotenüberdeckungen, Cliquen und stabile Mengen, Komplexität, Polynomialzeit, NP-Vollständigkeit, Hamiltonkreisproblem, Komplexitätsklasse, Damenproblem, Landau-Symbole, P-NP-Problem, Parametrisierter Algorithmus, Partitionierungsproblem, Modelltheorie, Springerproblem, Master-Theorem, Hüllenoperator, Nichtdeterministische Turingmaschine, Zweikellerautomat, Zeitkomplexität, Turingmaschine Typ 2, Reduktion, Problemkern, Maschinengestütztes Beweisen, Erfüllbarkeitsproblem für quantifizierte boolesche Formeln, Substitutionsmethode, Alternierende Turingmaschine, Rucksackproblem, Orakel-Turingmaschine, Satz von Cook, The Complexity of Songs, Untermengensumme, Partitionsproblem, Erfüllbarkeitsproblem der Aussagenlogik, Maximaler Schnitt, Längster kreuzungsfreier Springerpfad, Interaktives Beweissystem, Akra-Bazzi-Theorem, Deskriptive Komplexitätstheorie, PCP-Theorem, Cliquenproblem, Feedback Vertex Set, 3-SAT, Polynomialzeithierarchie, Karps 21 NP-vollständige Probleme, Registermaschine, Kontextsensitive Sprache, Platzkomplexität, NP-Schwere, Erreichbarkeitsproblem in Graphen, Hitting-Set-Problem, Pseudopolynomiell, Hilfskellermaschine, Wortproblem, Circuit Value Problem, Kurodas Problem, Problem der exakten Überdeckung, Lückensatz von Borodin, Mengenüberdeckungsproblem, Mengenpackungsproblem, Polynomialzeitreduktion, Akzeptieren, Ladner-Theorem, Satz von Savitch, Logarithmisch platzbeschränkte Reduktion, Feedback Arc Set, Knotenüberdeckungsproblem, Union-Theorem, Mengenzerlegungsproblem, NP-Äquivalenz, Dreifarbenproblem, NP-leicht. Auszug: 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. Die Komplexitätstheorie in der Theoretischen InformatikDie Komplexitätstheorie gilt, neben der Berechenbarkeitstheorie und der Theorie der Formalen Sprachen, als einer der drei Hauptbereiche der Theoretischen Informatik. Zu ihren wesentlichen Forschungszielen gehört die Klassifizierung von Problemen im Hinblick auf den zu ihrer Lösung notwendigen Aufwand. Eine besondere Rolle spielt dabei die Abgrenzung der praktisch effizient lösbaren Probleme. Die Komplexitätstheorie grenzt daher diejenigen Probleme ein, in denen andere Disziplinen der Informatik überhaupt sinnvollerweise nach effizienten Lösungen suchen sollten und motiviert so die Entwicklung von praxistauglichen Approximationsalgorithmen. Neben dem reinen Erkenntnisgewinn bereichert auch das Methodenarsenal der komplexitätstheoretischen Forschung zahlreiche angrenzende Gebiete. So führt etwa ihre enge Verzahnung mit der Automatentheorie zu neuen Maschinenmodellen und einem umfass...