Neben der Frage, wie ein Problem algorithmisch gelöst werden kann, ist auch die Frage nach der Effizienz einer solchen algorithmischen Lösung fundamentaler Bestandteil der Informatik. Die Komplexitätstheorie beschäftigt sich mit der Frage, welchen Ressourcenaufwand die Lösung ein Problems erfordert.
Da eine absolute Klassifikation von Problemen sich als sehr schwierig erwiesen hat, ist man zu einer relativen Klassifikation übergegangen. Dabei spielt der Begriff der Reduktion eine zentrale Rolle.
Wir arbeiten insbesondere im Bereich der Circuit Complexity.
