Abstract
The Product Homomorphism Problem (PHP) involves determining the existence of a homomorphism from a direct product of finite relational structures $A_1, \dots, A_n$ to a target structure $B$. While the problem is naturally contained in NExpTime, existing proofs of its NExpTime-completeness have traditionally relied on structures with unbounded arity. This paper provides a self-contained proof that PHP remains NExpTime-complete even under significant structural restrictions, such as for directed graphs or structures with bounded domain sizes. Furthermore, these results are applied to demonstrate that the Conjunctive Query (CQ) definability problem is coNExpTime-hard even for basic database schemas.
Introduction
In the study of relational structures and database theory, homomorphisms provide a fundamental framework for understanding query evaluation and constraint satisfaction. The Product Homomorphism Problem (PHP) asks whether there exists a mapping from the direct product of a collection of structures $\mathcal{A} = \{A_1, \dots, A_n\}$ to a target structure $B$ that preserves all relations.
Because the domain of the direct product $A_1 \times \dots \times A_n$ grows exponentially relative to the size of the input structures, PHP is inherently a high-complexity problem. Specifically, it is contained in NExpTime. Previous literature established its NExpTime-completeness, but these proofs utilized relations of unbounded arity—meaning the number of elements involved in a single relationship could grow with the input size. This research investigates whether the problem's hardness persists when the "complexity" of individual structures is strictly limited.
Hardness of Simple Structures
The core contribution of this work is proving that the exponential explosion of the direct product is sufficient to drive NExpTime-completeness, even when the individual components are remarkably simple.
Reduction from Exponential Tiling
The authors establish NExpTime-hardness through a reduction from the exponential tiling problem. By mapping the tiling constraints to a PHP instance where each structure $A_i$ has a domain size of only two elements (e.g., $\{0, 1\}$), they demonstrate that the interaction across the product space can simulate a $2^m \times 2^m$ grid. This proves that bounded domain size does not mitigate the problem's complexity.
Arity Reduction and Directed Graphs
A significant portion of the paper is dedicated to "arity reduction." The authors show how complex, high-arity relations can be encoded into a single binary relation (an edge in a graph). This is achieved through:
- Encoding Relations: Transforming multiple relations into a smaller set of relations without losing the hardness of the homomorphism problem.
- Gadget Construction: To prove the case for directed graphs, the authors use a gadget-based approach. Tuples of arity $r$ are represented as paths of length $r$, and "sink nodes" are introduced to ensure that any homomorphism from the product structure to the target structure preserves the intended logic.
These methods culminate in the finding that PHP is NExpTime-complete even for directed graphs (a single binary relation).
Application to CQ-Definability
The hardness results for PHP have direct implications for database theory, specifically the Conjunctive Query (CQ) definability problem (also known as the PP-definability problem). This problem asks whether a given relation can be defined by a Conjunctive Query—a standard "JOIN-SELECT-PROJECT" query—over a specific schema.
The paper establishes that CQ-definability is coNExpTime-hard even for the simplest possible database schema: a single table with two columns (a single binary relation). This improves upon earlier results that required relations of unbounded arity to prove similar hardness levels.
Conclusion
The findings of this paper suggest that the complexity of the Product Homomorphism Problem is robust against simplifications of the input structures. Whether the input consists of high-arity relations or simple directed graphs, the exponential nature of the direct product remains the dominant factor in computational difficulty.
For practitioners, these results highlight the inherent difficulty of certain meta-querying tasks in databases. For theorists, the paper identifies the "tractability frontier": PHP only becomes solvable in polynomial time when the number of relations, their arity, and the domain size are all simultaneously bounded. Future work may further refine these boundaries to identify specific subclasses of structures where the problem might be more manageable.
Summary updated