Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2305.01984 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915757905936384 |
|---|---|
| author | Bulín, Jakub Kompatscher, Michael |
| author_facet | Bulín, Jakub Kompatscher, Michael |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_01984 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Polynomial definability in constraint languages with few subpowers Bulín, Jakub Kompatscher, Michael Logic in Computer Science Logic Rings and Algebras 68T27, 08A70, 68Q25 F.4.1 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. |
| title | Polynomial definability in constraint languages with few subpowers |
| topic | Logic in Computer Science Logic Rings and Algebras 68T27, 08A70, 68Q25 F.4.1 |
| url | https://arxiv.org/abs/2305.01984 |