Two-element structures modulo primitive positive constructability

Abstract

Primitive positive constructions have been introduced in recent work of Barto, Opršal, and Pinsker to study the computational complexity of constraint satisfaction problems. Let ${\mathfrak{P}}_{\mathrm{fin}}$ be the poset which arises from ordering all finite relational structures by pp-constructability. This poset is infinite, but we do not know whether it is uncountable. In this paper, we give a complete description of the restriction ${\mathfrak{P}}_{\mathrm{Boole}}$ of ${\mathfrak{P}}_{\mathrm{fin}}$ to relational structures on a two-element set; in particular, we prove that ${\mathfrak{P}}_{\mathrm{Boole}}$ is a lattice. Finally, we use ${\mathfrak{P}}_{\mathrm{Boole}}$ to present the various complexity regimes of Boolean constraint satisfaction problems that were described by Allender, Bauland, Immerman, Schnoor and Vollmer.