💻 computer science

Polynomial definability in constraint languages with few subpowers

This paper investigates the conjecture that having few subpowers in a constraint language is equivalent to every primitive positive definable relation admitting a polynomial-length definition, a hypothesis verified for a large subclass including all three-element domains, with implications for bounding the complexity of the subpower membership problem to co-NP.

Original authors: Jakub Bulín, Michael Kompatscher

Published 2026-01-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jakub Bulín, Michael Kompatscher

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Constraint Puzzle"

Imagine you are trying to solve a giant puzzle. You have a set of rules (constraints) that tell you which combinations of pieces fit together. This is the Constraint Satisfaction Problem (CSP).

The Goal: Assign values to variables (like filling in a Sudoku grid) so that every rule is satisfied.
The Problem: Some puzzles are easy to solve; others are so complex that even the fastest supercomputers would take billions of years to find a solution.

Computer scientists want to know: What makes a puzzle easy or hard?

The Two Main Concepts

The paper focuses on two specific ways to describe how "complex" a set of rules is. Think of these as two different ways to measure the size of a library of puzzles.

1. "Few Subpowers" (The Library Size)

Imagine you have a small set of basic Lego bricks (your constraint language). You can build many different structures (relations) using these bricks.

The Concept: A language has "few subpowers" if the total number of unique structures you can build grows slowly (polynomially) as the structures get bigger.
The Analogy: It's like having a small, efficient toolbox. Even if you build a skyscraper, the number of unique blueprints you need to keep in your head doesn't explode into infinity; it stays manageable.
Why it matters: If a puzzle language has "few subpowers," we know there is a fast algorithm to solve it.

2. "Short Definitions" (The Recipe Length)

Now, imagine you want to describe one of those complex structures you built. You need a recipe (a logical formula) to tell someone exactly how to build it using your basic bricks.

The Concept: A language has "short definitions" if every structure you can build can be described by a recipe that isn't too long. Specifically, the length of the recipe should grow at a manageable rate (polynomially) as the structure gets bigger.
The Analogy: If you build a 100-story tower, a "short definition" means you can write the instructions on a single sheet of paper. A "long definition" would require a library of books just to describe how to stack the bricks.

The Big Question (The Conjecture)

The authors ask a simple question: Are these two concepts actually the same thing?

The Intuition: If you can only build a manageable number of structures (Few Subpowers), surely you shouldn't need a massive, book-length recipe to describe each one (Short Definitions).
The Conjecture: The authors guess that yes, they are equivalent. If a puzzle language is "small" in terms of the number of structures it can make, it must also be "small" in terms of how long it takes to write down the instructions for those structures.

What Did They Prove?

The authors didn't prove this for every possible puzzle in the universe, but they proved it for a very large and important group of them.

The Result: They showed that if the rules of the puzzle come from a specific type of mathematical structure (called an algebra that generates a "residually finite variety"), then the conjecture is true.
The "Three-Element" Breakthrough: A major highlight is that this proof works for all puzzles played on a 3-element domain (like a game with only Red, Green, and Blue pieces). Before this, we didn't know if the "short recipe" rule applied to all 3-color puzzles that were easy to solve. Now we do.

The "Compact Representation" Analogy

To prove this, the authors used a concept called Compact Representations.

The Metaphor: Imagine you have a massive, complex 3D sculpture. Usually, to describe it, you might need to list every single brick.
The Magic: For these specific types of puzzles, you don't need to list every brick. You only need a "signature" or a "skeleton" (a compact representation) that captures the essence of the shape.
The Connection: Because these skeletons are small (polynomial size), the authors could show that you can always write a short recipe (short definition) to recreate the full sculpture from that skeleton.

Why Does This Matter? (The "No" Certificate)

The paper also discusses a side benefit related to a problem called the Subpower Membership Problem (SMP).

The Problem: You are given a list of Lego pieces and a target shape. You need to decide: "Can I build this target shape using only these pieces?"
The "Yes" Answer: If the answer is "Yes," we already have a fast way to prove it (by showing the pieces fit).
The "No" Answer: If the answer is "No," it's usually hard to prove why it's impossible. You have to check every possibility.
The Paper's Insight: If the "Short Definitions" conjecture is true, then for these easy puzzles, we can also quickly prove the answer is "No." We can generate a short "certificate" (a short logical formula) that acts as a receipt saying, "No, this shape cannot be built from these pieces."

Summary

The Puzzle: Computer scientists study how to solve logic puzzles efficiently.
The Hypothesis: If a set of puzzle rules is "small" (doesn't create too many unique combinations), then the instructions for those combinations should also be "short."
The Proof: The authors proved this hypothesis is true for a huge class of puzzles, including all puzzles that use only three types of items.
The Takeaway: This confirms a deep link between the size of a puzzle's possibilities and the length of the instructions needed to describe them. It also suggests that for these puzzles, we can efficiently prove both when a solution exists and when it doesn't.

Technical Summary: Polynomial Definability in Constraint Languages with Few Subpowers

Problem Statement
The paper investigates the relationship between two structural properties of constraint languages (finite sets of relations $\Gamma$ ) within the framework of the Constraint Satisfaction Problem (CSP).

Few Subpowers: A constraint language $\Gamma$ has "few subpowers" if the number of $n$ -ary relations primitive positive (pp-) definable from $\Gamma$ is bounded by $2^{p(n)}$ for some polynomial $p(n)$ . This property characterizes a class of tractable CSPs where solution sets can be represented compactly (e.g., via generating sets).
Short PP-Definitions: A constraint language has "short pp-definitions" if every $n$ -ary relation pp-definable from $\Gamma$ can be defined by a primitive positive formula whose length (number of symbols) is polynomial in $n$ .

It is straightforward that short pp-definitions imply few subpowers, as there are only $2^{O(p(n))}$ formulas of length $p(n)$ . However, the converse was an open question. The authors propose Conjecture 1.1: A constraint language has short pp-definitions if and only if it has few subpowers.

Methodology
The authors employ a combination of constraint satisfaction theory and universal algebra.

Algebraic Characterization: They utilize the correspondence between constraint languages and their polymorphism algebras ( $Pol(\Gamma)$ ). The property of having few subpowers is characterized algebraically by the existence of a "k-edge polymorphism."
Critical Relations: The proof strategy reduces the general problem to analyzing "critical relations" (relations that are $\wedge$ -irreducible and have no dummy variables). The authors leverage the fact that any invariant relation can be decomposed into a conjunction of critical relations and projections.
Structural Analysis: The paper utilizes the theory of "linkedness congruences" and "parallelogram properties" of relations. A key step involves showing that under specific algebraic conditions, critical relations with the parallelogram property can be defined by pp-formulas of linear length.
Residual Finiteness: The main proof relies on the assumption that the variety generated by the polymorphism algebra, $HSP(A)$, is residually finite (containing only finitely many subdirectly irreducible algebras up to isomorphism, all of which are finite). This allows the authors to bound the arity of the relational basis required to define the relations.

Key Contributions and Results

Verification of the Conjecture for a Large Subclass: The paper's primary result (Theorem 4.6) confirms Conjecture 1.1 for any constraint language whose polymorphism algebra generates a residually finite variety. Specifically, if such an algebra has a $k$ -edge term, it admits pp-definitions of length $O(n^{\max(2, k-1)})$ .
Three-Element Domains: As a direct corollary (Corollary 4.7), the conjecture is proven for all constraint languages on a three-element domain. This is significant because 3-element domains exhibit complex behavior that does not always fall into the simpler categories of Mal'tsev or near-unanimity polymorphisms found in Boolean cases.
Boolean Case Confirmation: The paper re-confirms that the conjecture holds for Boolean (2-element) domains, where languages with few subpowers are known to have either majority or affine polymorphisms, both of which yield quadratic-length definitions.
Connection to Subpower Membership Problem (SMP): The authors analyze the Subpower Membership Problem, which asks if a tuple belongs to the subalgebra generated by a set of tuples.
- They argue that if a language has short pp-definitions, the "No" instances of SMP can be certified by a short pp-formula.
- This places the SMP for algebras with short pp-definitions in NP $\cap$ co-NP (Theorem 5.1).
- Consequently, if Conjecture 1.1 is true, then SMP for all algebras with few subpowers is in NP $\cap$ co-NP.
Counter-Examples and Limits: The paper notes that the condition of residual finiteness is sufficient but not strictly necessary for the conjecture to hold. They provide an example (Example 6.1) of a 4-element algebra that generates a non-residually finite variety yet still possesses short pp-definitions, suggesting the conjecture may hold more broadly.

Significance and Claims
The paper claims that establishing the equivalence between "few subpowers" and "short pp-definitions" is a fundamental step in understanding the complexity landscape of CSPs.

Theoretical Unification: It unifies the algebraic notion of "few subpowers" (related to the size of the relational clone) with the logical notion of "short definitions" (related to the complexity of the defining formulas).
Complexity Implications: The results suggest that for the large class of algebras with few subpowers (specifically those with residually finite varieties), the Subpower Membership Problem is not only in NP but also in co-NP.
Open Directions: The authors modestly note that while they have proven the conjecture for residually finite varieties, the general case remains open. They highlight that the condition of residual finiteness has traditionally been less central in CSP studies than in pure algebra, and extending these results to non-residually finite varieties is a necessary step for a complete resolution of the conjecture and the SMP problem. They also raise the question of whether short pp-definitions can be efficiently computed from generators, which would place SMP in P.