Short Definitions in Constraint Languages

A first-order formula is called primitive positive (pp) if it only admits the use of existential quantifiers and conjunction. Pp-formulas are a central concept in (fixed-template) constraint satisfaction since CSP(Γ) can be viewed as the problem of deciding the primitive positive theory of Γ, and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages Γ is characterized by having few subpowers, that is, the number of n-ary relations pp-definable from Γ is bounded by 2^p(n) for some polynomial p(n). In this paper we study a restriction of this property, stating 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 Γ having few subpowers, and verify this conjecture for a large subclass that, in particular, includes all constraint languages on three-element domains. We furthermore discuss how our conjecture imposes an upper complexity bound of co-NP on the subpower membership problem of algebras with few subpowers.

Authors

• Jakub Bulín
• Michael Kompatscher

Keywords

• constraint satisfaction
• primitive positive definability
• few subpowers
• polynomially expressive
• relational clone
• subpower membership