Von der Turingmaschine zum Quantencomputer - ein Gang durch die Geschichte der Komplexitätstheorie
J. Köbler, O. Beyersdorff
Abstract:
Die Komplexitätstheorie beschäftigt sich mit der Abschätzung des
Aufwands, der zur Lösung algorithmischer Probleme nötig ist.
In diesem Aufsatz verfolgen wir die spannende Entwicklung dieses
Teilgebietes der Theoretischen Informatik von ihren Wurzeln in
den 30er Jahren des 20. Jahrhunderts bis in die heutige Zeit.