| TDDB45 | Computability and Complexity Theory, ECTS-points /BERÄKNINGSBARHET OCH KOMPLEXITETSTEORI/ Advancement level: D | |
| Aim: The systematic study of computability and complexity theory has developed into one of the central and most active research areas of theoretical computer science. The aim of this course is to present the most significant results obtained in this area of research.Prerequisites: Basic knowledge of formal languages, automata theory, design and analysis of algorithms, and discrete mathematics.Supplementary courses: TDDA32 Design and analysis of algorithms.Course organization: The course consists of twelve lectures.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, interactive proof systems, models of parallel computers and parallel algorithms.Course literature: Bovet, D.P., Crescenzi, P., Introduction to the Theory of Complexity. First edition | ||
| UPG1 | Obligatory homework assignments. | |