Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Komplexität und Kryptografie

Humboldt-Universität zu Berlin | Mathematisch-Naturwissenschaftliche Fakultät | Institut für Informatik | Komplexität und Kryptografie | Publikationen | Abstracts | Von der Turingmaschine zum Quantencomputer - ein Gang durch die Geschichte der Komplexitätstheorie

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.