Jakub Bulín

Polynomial Definability in Constraint Languages with Few Subpowers

Abstract. A first-order formula is called primitive positive (pp) if it uses only existential quantifiers and conjunctions. Primitive positive formulas are a central concept in (fixed-template) constraint satisfaction, as [Formula: see text] can be viewed as the problem of decidi...