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
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
