Humboldt-Universität zu Berlin - Faculty of Mathematics and Natural Sciences - Complexity and Cryptography

Humboldt-Universität zu Berlin | Faculty of Mathematics and Natural Sciences | Department of Computer Science | Complexity and Cryptography | People | Olaf Beyersdorff | 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.

PDF-File:  turing.pdf