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

a course during the 19th European Summer School in Logic, Language, and Information (ESSLLI2007)


Post's lattice is the lattice of all classes of Boolean functions that contain the identity functions and are closed under composition - these classes are also known as clones. In the past few years, this lattice found many applications in computer science, among others it has turned out to be a powerful tool for complexity-theoretic studies of problems related to Boolean circuits, propositional formulas, and constraint satisfaction.

In this course we will give a basic introduction to Post's lattice and demonstrate its applications in complexity theory.

Overview of the lecture

  • Boolean functions and closed classes
  • Complexity of membership problems
  • Applications: Boolean circuits and propositional logic
  • Applications: Modal logic and database problems
  • Applications: Constraint satisfaction problems

The course will be aimed at advanced Masters or Ph.D. students with a minimal background in computational complexity (basic time and space bounded classes such as LogSpace, PTime, NPTime, basic reducibilities). It will introduce them to the lattice of Boolean clones and its applications and will lead them to the study of current research problems in the field.