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