Computation and Complexity Theory I


Aim of the course

The goal is to familiarize students with formal models of computation, analysis methods of the time and memory complexity of computational problems, determinating of the limits of computability.

Lecture programme

Language and issues of decision-making. Turing machine (deterministic and nondeterministic, modifications). The concept of the Turing machine computability. Other models of computation. Turing-Church principle. Undecidable problems. Halt problem. The concept of reduction between computational problems. The use of reduction in proofs of undecidability. Time complexity for deterministic Turing machine. Time complexity of nondeterministic Turing machine. Classes P and NP. The concept of NP-completeness. NP-complete problems. Examples of algorithms for NP-complete problems. The concept of weak NP-completeness. Properties of NP-complete and examples of trials to solve the P problem versus NP. Class NPI and Ladner’s theorem.

Overview of the course elements

Classes are aimed to strengthen and extend the knowledge gained at the lectures. During the classes the students solve the tasks in the theory of computation and computational complexity (e.g., write programs for Turing machine,prove the undecidability of assigned problems, demonstrate the properties of computation models and computational problems.)

Reading list

1. M. Sipser: Introduction to the theory of computation. WNT, Warsaw 2009
2. C.H. Papadimitriou: Computational complexity. WNT, Warsaw 2002
3. DP Bovet, P. Crescenzi: Introduction to the Theory of Complexity. Prentice Hall, 1994
4. I. Wegener: Complexity Theory, Springer, 2005
5. Kościelski A.: Theory of computation. Publishing House of the University of Wroclaw, Wroclaw 1997

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