Instructor: Georg Fuchsbauer, Krzysztof Pietrzak

Teaching Assistant: Michal Rybár

Complexity theory is a field on the border of mathematics and computer science with a remarkable list of celebrated achievements as well as vibrant present research activity. Complexity theory is the basic foundation of computer science, and it is concerned with classifying computational problems according to the resource (such as computation time and space) that are needed to solve them. This course is aimed at exposing students to the basic models of computation and the basic results and notion of complexity theory. The topics of the course include:

- Turing machine model of computation
- Diagonalization and undecidability
- Non-determinism in computation, and the class of NP problems
- Reductions and completeness
- ...

Students will get a problem sheet every Tuesday and will have one week to finish it and hand it in during the following week's lecture. It is advisable to discuss the solutions with fellow students, however, the final write-up must be done by each student on their own. Students will get the marked homework back during that week's recitation, where the solutions will be discussed and students will have the opportunity to ask follow-up questions. Depending on how much time there will be left, further problems outside of the problem sheets will be discussed.

Main: Michael Sipser, Introduction to the Theory of Computation, 2nd ed.

( http://books.google.at/books?id=SV2DQgAACAAJ&source=gbs_book_other_versions )

Background: Sanjeev Arora; Boaz Barak, Computational Complexity: A Modern Approach

( http://www.cs.princeton.edu/theory/complexity/ )

3 ECTS

Grades will be based on classroom participation, solutions to problem sheets (1/3 of the grade), and performance in a final exam (2/3 of the grade).

Date | Topic | Location | Other |
---|---|---|---|

Tuesday, November 25, 13:45 - 15:00 | Introduction to Turing Machines and Decidability | Mondi 3 | |

Thursday, November 27, 13:45 - 15:00 | Halting Problem and Reducibility | Mondi 3 | |

Thursday, November 27, 15:15 - 16:00 | Time complexity | Mondi 3 | |

Tuesday, December 2, 13:45 - 15:00 | Big Oh notation | Mondi 3 | |

Thursday, December 4, 13:45 - 15:00 | Decidability, P vs. NP | Mondi 3 | |

Thursday, December 4, 15:15 - 16:00 | First problem sheet | Mondi 3 | Recitation |

Tuesday, December 9, 13:45 - 15:00 | Reductions and space complexity | Mondi 3 | |

Thursday, December 11, 13:45 - 15:00 | Space complexity | Mondi 3 | |

Thursday, December 11, 15:15 - 16:00 | Second problem sheet | Mondi 3 | Recitation |

Tuesday, December 16, 13:45 - 15:00 | Sublinear space complexity | Mondi 3 | |

Thursday, December 18, 13:45 - 15:00 | Proof that NL = co-NL, Hierarchy Theorems | Mondi 3 | |

Thursday, December 18, 15:15 - 16:00 | Mondi 3 | Recitation | |

Thursday, January 8, 13:45 - 15:00 | Mondi 3 | ||

Thursday, January 8, 15:15 - 16:00 | Mondi 3 | Recitation | |

Tuesday, January 13, 13:45 - 15:00 | Mondi 3 | ||

Thursday, January 15, 13:45 - 15:00 | Mondi 3 | ||

Thursday, January 15, 15:15 - 16:00 | Mondi 3 | Recitation | |

Tuesday, January 20, 13:45 - 15:00 | Mondi 3 | ||

Thursday, January 22, 13:45 - 15:00 | Mondi 3 | ||

Thursday, January 22, 15:15 - 16:00 | Mondi 3 | Recitation | |

File | Due Date |
---|---|

Problem Sheet 1 | December 2nd |

Problem Sheet 2 | December 9th |

Problem Sheet 3 | December 16th |

Problem Sheet 4 | January 7th |

To take a look at the additional Downloads, please click here. (you must be logged in!)