Select your language

   +(36) 88 624 023 | |    H-8200, Veszprem, Egyetem str. 10, Building I.

Select your language

Responsible lecturer: István Heckl, associate professor (

Assumed preliminary studies
Theory of digital computation I


  1. Computational complexity;
  2. Time bounded Turing machines; Time-bounded simulation
  3. The classes P and NP; NP completeness
  4. Some NP-complete problems I (bounded tiling problem, integer programming)
  5. Some NP-complete problems II (travelling salesman problem)
  6. The complexity hierarchy
  7. Equivalence and normal forms; Compactness
  8. Structures and satisfiability
  9. Unsolvability and NP-completeness


Lewis, H. R. and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, New Jersey, 1981.

Alagar, V. S, Fundamentals of Computing, Prentice-Hall, New Jersey, 1989. 

Caroll, J. and D. Long, Theory of Finite Automata, Prentice-Hall, New Jersey, 1989.