The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Post's lattice with applications to complexity theory (Part III)

Vollmer, H (Hannover)
Monday 05 June 2006, 11:00-12:00

Seminar Room 1, Newton Institute


In this sequence of lectures we will give a basic introduction to Post's lattice of all sets of Boolean functions closed under superposition (a.k.a. clones), and show how to make use of this structure to obtain complexiy classifications of diverse problems for Boolean circuits, propositional formulas, databases, and Boolean constraint satisfaction problems.


[pdf ]


MP3MP3 Real AudioReal Audio

Back to top ∧