skip to content
 

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

Date: 
Tuesday 30th May 2006 - 11:00 to 12:00
Venue: 
INI Seminar Room 1
Abstract: 

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.

Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons