License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2023.28
URN: urn:nbn:de:0030-drops-185629
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18562/
Go to the corresponding LIPIcs Volume Portal

Bulín, Jakub ; Kompatscher, Michael

Short Definitions in Constraint Languages

pdf-format:
LIPIcs-MFCS-2023-28.pdf (0.7 MB)

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(Γ) 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.

BibTeX - Entry

@InProceedings{bulin_et_al:LIPIcs.MFCS.2023.28,
  author =	{Bul{\'\i}n, Jakub and Kompatscher, Michael},
  title =	{{Short Definitions in Constraint Languages}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18562},
  URN =		{urn:nbn:de:0030-drops-185629},
  doi =		{10.4230/LIPIcs.MFCS.2023.28},
  annote =	{Keywords: constraint satisfaction, primitive positive definability, few subpowers, polynomially expressive, relational clone, subpower membership}
}

Keywords: constraint satisfaction, primitive positive definability, few subpowers, polynomially expressive, relational clone, subpower membership
Collection: 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Issue Date: 2023
Date of publication: 21.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI