I7 Logo
Chair for Foundations of Software Reliability and Theoretical Computer Science
Informatik Logo TUM Logo
Courses

Übung zu Komplexitätstheorie
held by: Dr. Christian Schallhart
held in: SS 2006
sws: 2
Weitere Informationen, Literatur und Übungsblätter
downloadable material:
problem sets
title / description download
Blatt 1
O-Notation, Palindrome auf TMs, Klassen und Probleme, Festes Wortproblem
click here...
Blatt 2
Zeit- und Platzkonstruierbarkeit, Platzbeschraenkte Berechnungen, Membership von Problemen, Übersetzung von Problemen
click here...
Blatt 3
Logspace Reduktionen, DSPACE(n)!=P, Reduktionen
click here...
Blatt 4
Upward Translation, Abschlusseigenschaften, Alternation
click here...