Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2305.01984 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of 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.