Complexity theory

Lecture:	Wed 14-16, Fri 11-13 (E1 3, HS 003)
Tutorial:	Tue 16-18 (Geb. E2 5 (ex 27.2), Seminarraum 1) Fri 14-16 (Geb. E1 1 (ex 36.1), UG, U 12) TAs: Kanela Kaligosi, Evangelia Pyrga, Saurabh Ray kaligosiatmpi-sb..., pyrgaatmpi-sb..., saurabhatmpi-sb... Here is a list of people that registered so far. (Nov 13, 2005)
Grades:	40% midterm (requirement: 50% of exercises so far) 60% endterm (requirement: 50% of all exercises)
Examination dates: Midterm: Dec 16, 2005, 11-13, HS 001 and 003 Endterm: Feb 24, 2006, 9-12, HS 001 and 002 Re-exam: Apr 03, 2006, 14-17, HS 001

Information regarding the exams

General:

You may bring a DinA4 sheet (i.e. 2 pages) with hand written notes on it. No photocopies of someone else's notes.
No pocket calculators, mobile phones, books, etc.
You have to pass the midterm and the endterm exam. If you fail at least one of them, you can write the re-exam. You have to pass this one then. If you failed both the midterm and the endterm, the grade of the re-exam is your final grade. If you only failed in exactly one of these exams and the grade in the re-exam is worse than the grade of the other exam that you passed, you will get a weighted mean of the grades of the two exams (60% re-exam). If you failed in exactly one of midterm and endterm exam and your grade in the re-exam is better than the grade of the other exam that you passed, your final grade is the grade of the re-exam. And yes, you can also write the re-exam if you passed both the midterm and the endterm. Your grade will be the better of 100% re-exam, 60% re-exam and 40% (better of midterm and endterm), or 60% endterm and 40% midterm.

Midterm:

Here is a list of the people qualified for the midterm exam. If you do not appear at all on the list or your immatriculation number is not marked by yes, but you think it should, contact me immediately.
Please be at 11:00 in the lecture room for the midterm exam. We start 11:15 and end 13:00.
Midterm exam (posted Dec 21, 2005) and solutions (posted Jan 10, 2006)
Here are two proofs of Ladner's theorem (external link).
Results of the midterm exam (posted Dec 29, 2005)
You can have a look at your exam on Friday, Jan 13 right after the lecture. Or make an appointment (via email).

Endterm:

Here is a list of the people qualified for the endterm exam.
Please be at 9:00 in the lecture room for the endterm exam. We start at 9:15 and write until 11:45. The amount of assignments will be the same as for the midterm, so there should be enough time.
Again, you may use one Din A4 sheet with hand written notes.
You can skip the endterm and still write the re-exam.
The relevant chapters for the end term are Chapters 14 to 20. But you still habe to know what NP is etc.
Endterm exam and Solutions (posted Mar 3, 2006)
Results of the endterm exam (posted Feb 28, 2006)
If you want to have a look at your exam, contact me via email.

Re-exam:

All people that qualified for the endterm, qualified for the re-exam, too.
You do not have to register, just come (or don't).
Again you may bring one (not two!) Din A4 sheet (i.e. two pages) with handwritten notes.
The relevant chapters are 1 to 12 and 14 to 20.
We start at 14:00 and write for three hours, the amount of assignments will be slightly larger than in the midterm exam.
Results of the re-exam
Re-exam and solutions
If you want to have a look at your exam, contact me via email.

Lectures notes

Part 1 (posted Oct 18, 2005)
Part 2 (posted Oct 20, 2005, last revision Nov 9, 2005)
Part 3 (posted Oct 26, 2005, last revision Oct 28, 2005)
Part 4 (posted Oct 28, 2005, last revision Nov 10, 2005)
Part 5 (posted Nov 4, 2005, last revision Nov 23, 2005)
I fixed the hole in the proof of Theorem 5.7. It was not that large as I thought during the lecture. Sorry, I was just confused. (posted Nov 10, 2005)
Part 6 (posted Nov 9, 2005, last revision Nov 18, 2005)
Part 7 (posted Nov 11, 2005, last revision Nov 18, 2005)
Part 8 (posted Nov 18, 2005, last revision Nov 25, 2005)
Part 9 (posted Nov 23, 2005)
Part 10 (posted Nov 25, 2005, last revision Nov 30, 2005)
Part 11 (posted Nov 30, 2005, last revision Dec 1, 2005)
Part 12 (posted Dec 9, 2005)
Part 13 (posted Dec 9, 2005, somewhat preliminary)
Part 14 (posted Dec 21, 2005)
Part 15 (posted Jan 10, 2006)
Part 16 (posted Jan 13, 2006)
Part 17 (posted Jan 18, 2006, last revision Jan 21, 2006)
Part 18 (posted Jan 25, 2006, last revision Feb 8, 2006)
Part 19 (posted way too late Feb 1, 2006)
Part 20 (posted Feb 3, 2006, last revision Feb 08, 2006)
Part 21 (posted Feb 08, 2006, last revision Feb 10, 2006)
Part 22 (posted Feb 08, 2006, last revision Feb 10, 2006)
Part 23 (posted Feb 10, 2006)

Exercises

Home work 1 (posted Oct 20, 2005)
Exercise 3: Since a TM can never write a blank by convention, the 0 in the definition of space complexity of S has to replaced by a 1. Sorry. (posted Oct 23, 2005)
The statement in the brackets is somewhat misleading. The removal of the +c will increase the space complexity (to c). (posted Oct 23, 2005)
Kanela Kaligosi, Evangelia Pyrga, and Saurabh Ray came up with a solution that removes the +c and and keeps the space bound 1. (posted Oct 26, 2005)
Home work 2 (posted Oct 28, 2005)
Home work 3 (posted Nov 04, 2005)
Exercise 7: As stated on the sheet, the exercise is not easy to prove. Assume that s_2 o f is space constructible, too.
Home work 4 (posted Nov 11, 2005)
Home work 5 (posted Nov 18, 2005)
Exercise 17: t should be simultaneously constructible in space s and time t.
Exercise 18: As in Exercise 17, t should be time constructible.
Home work 6 (posted Nov 25, 2005)
Home work 7 (posted Dec 1, 2005)
Here are solutions of home work 7.
Sample exercises for midterm (posted Dec 2, 2005)
Home work 8 (posted Dec 21, 2005) and solutions (posted Jan 21, 2006)
Home work 9 (posted Jan 13, 2006) and a solution of Exercise 29 (posted Jan 25, 2006)
Home work 10 (posted Jan 20, 2006)
Home work 11 (posted Jan 30, 2006)
Home work 12 (posted Feb 3, 2006)