FDA029 Complexity Theory

Lectures:

12 h

Recommended for

Graduate students.

The course was last given:

Spring 2000.

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 2002.

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.