Komplexitätstheorie

Sprachen, Probleme, Zeitkomplexität

NTM und die Klasse NP

NP-vollständige Probleme $\star$

Komplementsprache

Weitere Komplexitätsklassen über NP hinaus

Pseudopolynomiale Algorithmen $\star$

Approximationsalgorithmen für Optimierungsprobleme $\star$