Those interested in computability issues and complexity theory.
The course was last given
To give basic knowledge about computability and complexity theory.
CUGS Computation II or similar. Mathematical maturity is essential
Basic computability theory, complexity classes (P, NP, PSPACE...), reductions, approximability, randomness.
Bovet, D.P., Crescenzi, P.: Intoduction to the Theory of Complexity, Prentice
Detailed reading list will be given later together with a detailed course description.
Two sets of exercises. Deadlines will be decided later.
Given by Department of Computer Science, Linköping University
The course will be given during autumn 2004. The exact course format will be
decided when the number of students is known. Please register as soon as
possible if you intend to attend this course.
Important note: Consider the possibility of following the ugrad-course TDDB41 instead of Computation III. The contents of the courses are the same but there are more time for presenting the material and, more importantly, discussing it in TDDB41. Also note that the examination is identical. TDDB41 is given during spring 2004 (p. 2).
Course homepage: Not available yet. The TDDB41 homepage can be found here:
Page responsible: Director of Graduate Studies
Last updated: 2012-05-03