Computation and Complexity Theory II


Aim of the course

The lecture course continues the Theory of Computation and Computational Complexity I. The goal of the course is to familiarize students with advanced aspects of computational complexity theory and practical principles of coping with difficult computational problems.

Lecture programme

Computations with the oracle. Polynomial hierarchy. Memory complexity. Class PSPACE. Connections of polynomial hierarchy and PSPACE. Problem QBF. Theorems on time and memory hierarchy. Classes EXP and NEXP. Classes L and NL. The problem of L vs. NL. Problem NL vs. coNL. Approximate calculations. Approximation algorithms. Theorem PCP.

Overview of the course elements

The course comprises a project within which students solve a difficult computational problem. The aim of the project is to teach methods of dealing with solving problems for which are unknown, quick, accurate algorithms.

Reading list

1. Sipser M.: Wprowadzenie do teorii obliczeń. WNT, Warszawa 2009
2. Papadimitriou C.H.: Złożoność obliczeniowa. WNT, Warszawa 2002
3. Bovet D.P, Crescenzi P.: Introduction to the theory of complexity. Prentice Hall, 1994
4. Wegener I.: Complexity Theory, Springer, 2005
5. Kościelski A.: Teoria obliczeń. Wydawnictwo Uniwersytetu Wrocławskiego, Wrocław 1997

Copyright © 2010 Department of Computer Science   |   AGH University of Science and Technology   |   Created by Creative Bastards