BackEsc12510
Abstract Complexity Theory
Abstrakte Komplexitätstheorie
8 CPirregularlyDEno longer offered
Contents
Gödelnummerierung, Blumsches Maß, Speed-up-Theorem, Gap-Theorem, Union-Theorem, Naming-Theorem.
Learning outcomes
Einblick in die Grundlagen der Komplexitätstheorie. Die abstrakte Komplexitätstheorie löst sich ganz von den konkreten Aufwandsmaßen und Modellen. Sie definiert axiomatisch, welche Eigenschaften ein Maß haben soll, und leitet daraus Sätze ab, die für alle (vernünftigen) Maße gelten.
Assessment
Prüfungsgespräch benotet
Literature (1)
- Manuel Blum: A Machine-Independent Theory of the Complexity of Recursive Functions. J. ACM 14(2): 322-336 (1967)
Source: BTU's module description · retrieved 17 Oct 2026Original