Komplexitätstheorie

Im Rahmen der Komplexitatstheorie wird versucht, die Schwierigkeit von Problemen durch den Ressourcenverzehr zu messen, der durch die Problem- loesung verursacht wird. Zur Untersuchung dieser Problemschwierigkeit ("Komplexitat") werden der Loesungsaufwand fur den schlechtest denkmoeg- lichen Fall (worst case-Analysen) oder der durchschnittlich zu erwartende Loesungsaufwand (average case-Analysen) betrachtet. Wesentl iche Analyse- konzepte der Komplexitatstheorie stellen Entscheidungsprobleme und Turing-Automaten dar. Auf ihrer Grundlage lassen sich Komplexitatsklassen von Problemen bilden. Diese Problemklassen und die ihnen zugehoerige Pro- blemschwierigkeit bilden ein Fundament, aus dem Empfehlungen fur erfolg- versprechende Loesungsalgorithmen abgeleitet werden koennen. Einen Schwerpunkt bildet die Klasse der NP-vollstandigen Probleme. Sie zeichnen sich dadurch aus, dass ihre Loesung einerseits besonders aufwendig ist. Andererseits besitzen sie fur die Bewaltigung zahlreicher praktisch inter- essanter Aufgaben aus dem Bereich des Operations Research eine heraus- ragende Rolle. Hierzu gehoeren beispielsweise die Planung von Transport- routen, das Festlegen von Standorten fur Auslieferungslager oder die inner- betriebliche Belegung von Maschinen mit Fertigungsauftragen. Es werden neuere Erkenntnisse der Komplexitatstheorie vorgestellt, welche die Klasse NP-vollstandiger Probleme intern differenzieren und uber sie hinausfuhren. Einschrankungen solcher Analysen werden an hand mehrfacher Validitats- probleme aufgezeigt.