Two-element structures modulo primitive positive constructability

摘要

Primitive positive constructions have been introduced in recent work of Barto, Opr.sal, and Pinsker to study the computational complexity of constraint satisfaction problems. Let Pfin 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 article, we give a complete description of the restriction PBoole of Pfin to relational structures on a two-element set. We use PBoole to present the various complexity regimes of Boolean constraint satisfaction problems that were described by Allender, Bauland, Immerman, Schnoor and Vollmer.