Komplexitätstheorie

Die Komplexitätstheorie beschäftigt sich damit, generelle Aussagen über die Komplexität von Problemen bzw. zugehörigen Optimierungsmodellen sowie über den Rechenaufwand von Algorithmen zu treffen. Beide Aspekte hängen eng miteinander zusammen. Lässt sich der Rechenaufwand eines Algorithmus durch ein von der Problemgröße (z.B. Anzahl der Kunden oder Produkte) abhängiges Polynom nach oben beschränken, so spricht man von einem effizienten Verfahren. Bei nichteffizienten Verfahren wächst die Rechenzeit ebenso wie die Lösungsmenge mit zunehmender Problemgröße exponentiell. Probleme bzw. Modelle, für die ein effizientes Lösungsverfahren bekannt ist, werden als polynomial lösbar und die übrigen als NP-schwer bezeichnet. Während z.B. LP-Modelle und Kürzeste-Wege-Probleme polynomial lösbar sind, gehören die meisten Probleme der kombinatorischen Optimierung zur Klasse der NP-schweren Probleme. Für polynomial lösbare Probleme sollte immer ein exaktes Verfahren angewendet werden. Bei NP-schweren Problemen in praxis-relevanten Größenordnungen ist der Einsatz von Heuristiken angezeigt.

Vorhergehender Fachbegriff: Komplexitätskosten | Nächster Fachbegriff: Komponentenanbieter

Diesen Artikel der Redaktion als fehlerhaft melden & zur Bearbeitung vormerken

Weitere Begriffe : VerbrKrG | Organisationstheorien | Baumgraph

Praxisnahe Definitionen

Nutzen Sie die jeweilige Begriffserklärung bei Ihrer täglichen Arbeit. Jede Definition ist wesentlich umfangreicher angelegt als in einem gewöhnlichen Glossar.

Marketing

Definition

Konditionenpolitik

Fachbegriffe der Volkswirtschaft

Die Volkswirtschaftslehre stellt einen Grossteil der Fachtermini vor, die Sie in diesem Lexikon finden werden. Viele Begriffe aus der Finanzwelt stehen im Schnittbereich von Betriebswirtschafts- und Volkswirtschaftslehre.

Investitionsrechnungen

Marktversagen

Umsatzsteuer