Eine freie Initiative von Menschen bei  anthrowiki.at,  anthro.world,  biodyn.wiki und  steiner.wikimit online Lesekreisen, Übungsgruppen, Vorträgen ... |
 Wie Sie die Entwicklung von AnthroWiki durch Ihre Spende unterstützen können, erfahren Sie hier.
|
|
|
Use Google Translate for a raw translation of our pages into more than 100 languages. Please note that some mistranslations can occur due to machine translation. |
Komplexitätstheorie
Die Komplexitätstheorie ist neben der Berechenbarkeitstheorie ein zentrales Arbeitsgebiet der theoretischen Informatik. Während die Berechenbarkeitstheorie feststellt, ob ein bestimmtes Problem überhaupt algorithmisch lösbar ist, untersucht und klassifiziert die Komplexitätstheorie die Menge aller lösbaren Probleme auf verschiedenen formalen Rechnermodellen hinsichtlich ihrer Komplexität. Häufig in der Komplexitätstheorie eingesetzte Rechnermodelle sind Turingmaschinen, Registermaschinen, endliche Automaten und Kellerautomaten.
Die Komplexität misst sich vor allem am Bedarf von Rechenzeit und Speicherplatz. Der Ressourcenverbrauch kann beispielsweise linear, polynomial, exponentiell oder gar überexponentiell steigen. Probleme, die mit einer deterministischen Turingmaschine in Polynomialzeit lösbar sind, werden als praktisch lösbar angesehen.
Siehe auch
- Komplexitätstheorie - Artikel in der deutschen Wikipedia
