Seminar: Computability and Complexity II

Dr. Heinrich Rolletschek

March 7, 2008

Time and place:

Friday, 9:00-10:30, seminar room Schloß Hagenberg. This schedule is provisorial and may later be changed.

Preliminary meeting:

Friday, March 7 2008, 9: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 Blum's abstract complexity theory; other topics will be decided about later.

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.
• C. Papadimitriou: Computational Complexity. Addision-Wesley 1994.
• G. Tourlakis: Computability. Reston Publishing Company 1984.

Assessment:

Grades will be based on presentations given in the seminar.