Complexity Theory

Lectures
12 h

Recommended for
Graduate students.

The course was last given
Spring 1998

Goals
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 of this research.

Prerequisites
It is recommended that students of this course have some prior knowledge of formal languages, automata theory, design and analysis of algorithms, and discrete mathematics.

Contents
The course covers 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.

Literature
Bovet, D.P., Crescenzi, P.: Introduction to the Theory of Complexity. First edition.
For the computability part of the course, it is recommended to have access to Hopcroft, J.E., Ullman, J.D.:Introduction to Automata Theory, Languages, and Computation.

Teachers
Peter Jonsson.

Examiner
Peter Jonsson.

Schedule
Spring 2000.

Examination
Students are assessed by three sets of homework assignments. Each set gives a total of 12 points; to pass the course, a student should have at least 8 points from each set.

Credit
3 credits

Comments
The course will be given in Swedish. Examination can, on request, be given in English.

Page responsible: Director of Graduate Studies