IST Austria Courses
IST Austria logo

Computational Complexity

Instructor: Georg Fuchsbauer, Krzysztof Pietrzak

Teaching Assistant: Michal Rybár

Description

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:


Problem sheets

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. 


Textbooks

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


Credits

 3 ECTS


Final Grade

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

Schedule (subject to change)

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
       

Homework

File Due Date
Problem Sheet 1 December 2nd
Problem Sheet 2 December 9th
Problem Sheet 3 December 16th
Problem Sheet 4 January 7th

Additional Downloads

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

Examples for Problem Sheet 1