Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
Logo Leibniz Universität Hannover
Logo:Institut für Theoretische Informatik
  • Zielgruppen
  • Suche
 

Description

Finite model-theory, as an interdisciplinary subject between mathematics and computer science, has been particularly successfully applied in the study of complexity classes defined by Boolean circuits.

In this course, we will discuss in detail logical characterizations known for the classes AC0, TC0, NC1 (see [1] below) and the very recent characterization of SAC1

  • logical reductions
  • generalized quantifiers given by different groupoid word problems
  • built-in relations: addition and multiplication vs. the bit-predicate.

We will discuss applications from a complexity theoretic point of view as well as consequences for the expressive power of certain logical languages.

The course will be aimed at advanced Masters or Ph.D. students with a minimal background in elementary first-order logic and computation (Turing machines, basic time and space bounded classes as LogSpace, PTime, NPTime). It will lead them from the basic concepts in circuit complexity to the study of current research problems in the field.

  • References

    1. Heribert Vollmer, Introduction to Circuit Complexity, Springer 1999.
    2. C. Lautemann, P. McKenzie, T. Schwentick, H. Vollmer, The descriptive complexity approach to LOGCFL; Journal of Computer and Systems Sciences, 62(4),629-652, 2001

  • Lecture Notes (postscript file)

Logic and Circuit Complexity on the Web