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 deciding the primitive positive theory of [Formula: see text], and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages [Formula: see text] is characterized by the property of having few subpowers, meaning that the number of [Formula: see text]-ary relations pp-definable from [Formula: see text] is bounded by [Formula: see text] for some polynomial [Formula: see text]. In this paper, we study a restriction of this property, namely that every pp-definable relation is definable by a pp-formula of polynomial length. We conjecture that the existence of such short definitions is actually equivalent to [Formula: see text] having few subpowers, and we verify this conjecture for a large subclass, which, in particular, includes all constraint languages on three-element domains. Furthermore, we discuss how our conjecture imposes an upper complexity bound of [Formula: see text] on the subpower membership problem for algebras with few subpowers.