Komplexitätstheorie

Im Mittelpunkt der Komplexitätstheorie steht der Ressourcenverbrauch von Algorithmen. Dabei steht insbesondere der Bedarf an Zeit und Speicher im Fokus. Damit lotet die Komplexitätstheorie die Grenzen des algorithmisch Machbaren aus.

Um Algorithmen klassifizieren zu können, unterteilt man sie in bestimmte Komplexitätsklassen. Läuft der Algorithmus beispielsweise in quadratischer Zeit, dann weiß man sicher, dass das entsprechende Problem auch in quadratischer Zeit lösbar ist.

Generell unterscheidet man zwischen den drei Komplexitätsklassen P, NP und NP-vollständig. Dabei bezeichnet P die Menge aller Entscheidungsprobleme mit einem polynomialen Lösungsalgorithmus (O(nk)). Man spricht deshalb auch von „leichten“ Problemen. NP hingegen steht für die Menge aller nicht-deterministisch polynomial lösbaren Problemen. Bis heute weiß man nicht, ob P = NP gilt oder eben nicht (Millennium-Problem).

Relevant ist die Komplexitätstheorie unter anderem im Operations Research für Optimierungs- und Entscheidungsprobleme. Bei einem Optimierungsproblem besitzt jeder zulässige Punkt x einen Zielfunktionswert f(x) und man möchte den zulässigen Punkt finden, der den bestmöglichsten Zielfunktionswert liefert. Bei einem Entscheidungsproblem hingegen fragt man sich, ob es einen Punkt mit einem Zielfunktionswert höchstens/mindestens eines festen Wertes k gibt. Ein Optimierungsproblem wäre beispielsweise die Menge aller Traveling-Sales Probleme, während ein Entscheidungsproblem die Menge aller Rucksack-Probleme wäre.