Other subjects (outer of main subjects)

Responsible lecturer: István Heckl, associate professor (heckl@dcs.uni-pannon.hu)

Assumed preliminary studies:
Theory of digital computation I

Topics:

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

Literature:

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.