Komplexit��tstheorie

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.