Seminar: Computability and Complexity I

Dr. Heinrich Rolletschek

November 11, 2009

Time and place:

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

Contents:

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.

Literature:

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

Assessment:

Grades will be based on presentations given in the seminar.