SoSe 2011 » Advanced Complexity Theory
Ziegler

Übersicht

Downloads

Aktuelles

14.06.2011	Due to a conference the will be no lecture/exercises on June 24.
13.05.2011	Die für den 3.6. vorgesehene Vorlesung wird vorgezogen auf den 13.5. und den 20.5. jeweils um 13h30 bis 14h45
21.04.2011	Übung und Vorlesung wurden verschoben von Donnerstag auf Freitag (gleiche Uhrzeit und gleicher Ort)
08.04.2011	Vorbesprechung am 14.4. (Donnerstag) um 9h50 im S2|15-201

 

Veranstalter

Name	Raum	Tel.
Ziegler, Martin

 

Vorlesung

Tag	Uhrzeit	in Raum
Freitags	10:45 - 12:25	S2|15-201

 

Übung

Nr.	Zeit	in Raum	bei
1	Freitags, 9:50 - 10:35	S2|15-201	Martin Ziegler

 

Contents

1. Algorithmic Information Theory and Applications
   1. A lower bound for 1-tape Turing machines
2. Time versus Space
   1. Pebble Game: Time versus Space for Circuits
   2. Pebble Strategies and Computation
3. Simple Diagonalization: Hartmanis' Hierarchy Theorems
4. Relativization and Sophisticated Diagonalization
   1. Baker, Gill, and Solovay
   2. Friedberg and Muchnik
   Wanna earn $100 from Stephen Cook ?

    

   Impressum | Datenschutzerklärung