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.
- E. Böhler, H. Vollmer.
Boolean functions and Post's lattice with applications to complexity theory;
Lecture Notes for Logic et Interaction 2002, École thématique: Complexité et Calcul, Centre International de Rencontres Mathématiques, 2002.
- Boolean Constraint Satisfaction Problems, or: When Does Post's Lattice Help?
- Short course at Isaac Newton Institute, Cambridge: Part I, Part II, Part III
- M.Bauland, T. Schneider, H. Schnoor, I. Schnoor, H. Vollmer,
The Complexity of Generalized Satisfiability for Linear Temporal Logic (Slides of the talk on Friday).