Short definitions in constraint languages

arXiv2305.01984MaRDI QIDQ6435148FDOQ6435148

Authors: Jakub Bulín, Michael Kompatscher 

Publication date: 3 May 2023

Abstract: 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($Gamma$) can be viewed as the problem of deciding the primitive positive theory of $Gamma$, and pp-definability captures gadget reductions between CSPs. An important class of tractable constraint languages $Gamma$ is characterized by having few subpowers, that is, the number of $n$-ary relations pp-definable from $Gamma$ 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 $Gamma$ 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.

Mathematics Subject Classification ID

Applications of universal algebra in computer science (08A70)

This page was built for publication: Short definitions in constraint languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6435148)