# Seminar: Computability and Complexity I

## Dr. Heinrich Rolletschek

### November 11, 2009

Tuesday, 14:30-16:00, seminar room Schloß Hagenberg.

In general the seminar covers various classical areas of computability theory. This
semester it is planned to deal with polynomial-time complexity and NP-completeness in particular.

- W. Brainerd, L. Landweber:
*Theory of Computation*. Wiley 1974.
- M. Garey, D. Johnson:
*Computers and Intractability. A Guide to the Theory of NP-Completeness*.
Freeman & Company.
- J. Hopcroft, J. Ullman:
*Introduction to Automata Theory, Languages and Computation*. Addison-Wesley
1979.
- M. Sipser:
*Introduction to the Theory of Computation*. PWS Publishing Company 2005.
- R. Soare:
*Recursively Enumerable Sets and Degrees*. Springer 1986.
- G. Tourlakis:
*Computability*. Reston Publishing Company 1984.

Grades will be based on presentations given in the seminar.