Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Einführung in den aufwandsbezogenen Komplexitätsbegriff

Zusammenfassung
Die Komplexität von Problemen kann — ausgehend von einer gemeinsamen systemtheoretischen Betrachtungsweise1) — auf zwei grundsätzlich verschiedenen Ebenen untersucht werden. Auf der ersten Ebene wird die Struktur von Systemen analysiert, auf der zweiten dagegen ein spezieller Aspekt des Systemverhaltens.
Stephan Zelewski

2. Konzeptionelle Grundlagen der Komplexitätstheorie

Zusammenfassung
Ein Entscheidungsproblem15) ist ein Problem, das zu seiner Lösung die Auswahl zwischen zwei kontradiktorischen Alternativen erfordert. Es wird dem Entscheidungsträger eine Frage unterbreitet, die dieser nur durch ein “Ja” oder “Nein” zu beantworten vermag.
Stephan Zelewski

3. Anwendung der Komplexitätstheorie auf Probleme des Operations Research

Zusammenfassung
Die typischen Probleme des Operations Research, die zugleich als die “interessanten” Fragestellungen dieser Disziplin betrachtet werden können338), sind über die Problemklassen der Komplexitätstheorie nicht annähernd gleichmäßig verteilt. Vielmehr konzentrieren sich die meisten Entscheidungsprobleme auf die Klasse NP339). Unter diesen NP-komplexen Entscheidungsproblemen spielen wiederum die NP-vollständigen Probleme, deren korrespondierenden Optimierungsprobleme NP-hart sind340), die wichtigste Rolle341). Daher weisen die StandardKonzepte der Komplexitätstheorie nur eine geringe Trennschärfe hinsichtlich der Beurteilung der Schwierigkeit von OR-Problemen auf.
Stephan Zelewski

Backmatter

Weitere Informationen