TDDB41	Computability and Complexity Theory, 4,5 ECTS-points /Komplexitetsteori/ Advancement level: D
	Aim: The aim of this course is to present some of the most significant results obtained in complexity theory. Prerequisites: Basic knowledge of formal languages, automata theory, design and analysis of algorithms, and discrete mathematics. Probability theory and optimization Supplementary courses: TDDA 32 Design and analysis of algorithms. Course organization: The content of the course is presented during the lectures by the course leader and the participants. Course content: Elements of computability theory, complexity classes, the classes P and NP, complexity of optimization problems, beyond NP, space-complexity classes, probabilistic algorithms and complexity classes. Course literature: Bovet, D.P., Crescenzi, P., Introduction to the Theory of Complexity. First edition
UPG1	Obligatory homework assignments., 3 p.

Course language is swedish.