Im Rahmen der Komplexitätstheorie wird versucht, die Schwierigkeit von Problemen durch den Ressourcenverzehr zu messen, der durch die Problem- lösung verursacht wird. Zur Untersuchung dieser Problemschwierigkeit ("Komplexität") werden der Lösungsaufwand für den schlechtest denkmög- lichen Fall (worst case-Analysen) oder der durchschnittlich zu erwartende Lösungsaufwand (average case-Analysen) betrachtet. Wesentl iche Analyse- konzepte der Komplexitätstheorie stellen Entscheidungsprobleme und Turing-Automaten dar. Auf ihrer Grundlage lassen sich Komplexitätsklassen von Problemen bilden. Diese Problemklassen und die ihnen zugehörige Pro- blemschwierigkeit bilden ein Fundament, aus dem Empfehlungen für erfolg- versprechende Lösungsalgorithmen abgeleitet werden können. Einen Schwerpunkt bildet die Klasse der NP-vollständigen Probleme. Sie zeichnen sich dadurch aus, daß ihre Lösung einerseits besonders aufwendig ist. Andererseits besitzen sie für die Bewältigung zahlreicher praktisch inter- essanter Aufgaben aus dem Bereich des Operations Research eine heraus- ragende Rolle. Hierzu gehören beispielsweise die Planung von Transport- routen, das Festlegen von Standorten für Auslieferungslager oder die inner- betriebliche Belegung von Maschinen mit Fertigungsaufträgen. Es werden neuere Erkenntnisse der Komplexitätstheorie vorgestellt, welche die Klasse NP-vollständiger Probleme intern differenzieren und über sie hinausführen. Einschränkungen solcher Analysen werden an hand mehrfacher Validitäts- probleme aufgezeigt.

Spécifications