Komplexitätstheorie

Aus AnthroWiki
(Weitergeleitet von Polynomialzeit)

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