Abstract
Constraint Satisfaction Problems (CSPs) are typically NP-complete, posing significant computational challenges in artificial intelligence. This paper identifies specific classes of CSPs—those characterized by functional or bijective constraints—that can be solved in polynomial time. By leveraging arc and path consistency techniques and introducing the concept of a "root set" of variables, the author provides a framework for transforming these problems into backtrack-free searches with predictable complexity.
Introduction
CSPs are fundamental to various AI applications, including scheduling, planning, and VLSI design. Traditional approaches to managing their NP-complete nature focus on the structural properties of the constraint graph (e.g., tree-width) or the size of variable domains. This research shifts the focus toward the semantics of the constraints themselves. Specifically, it examines "functional" constraints (where one variable's value uniquely determines another's) and "bijective" constraints (one-to-one mappings). While common in practice, these properties have been under-utilized in formal complexity analysis.
Methodology: Consistency and Functionality
The core approach involves applying standard filtering techniques—Arc Consistency (AC) and Path Consistency (PC)—to functional and bijective relations. A key insight is that achieving consistency does not destroy the functional nature of the constraints; rather, it reveals induced functional relationships.
For bijective constraints, the author proves that AC and PC are sufficient to achieve global consistency. In such networks, any valid assignment for a single variable can be extended to a complete solution without backtracking. Furthermore, in a connected bijective CSP, all variable domains will converge to the same size after consistency filtering.
The Root Set Decomposition
To handle general functional constraints, the paper introduces the root set concept. A root set $R$ is a minimal group of variables from which all other variables in the functional constraint graph can be reached via directed functional paths.
The proposed algorithm follows four phases:
- Identification: Find a minimum root set $R$.
- Filtering: Apply AC and PC to prune the search space.
- Instantiation: Assign values to the variables in $R$.
- Extension: Propagate these values to the remaining variables. Due to the functional nature and established consistency, this step is guaranteed to be backtrack-free.
Key Results and Complexity
The complexity of solving a CSP with a root set $R$ is reduced from $O(d^n)$ to $O(n^3 d^3 + d^{|R|})$, where $d$ is the domain size and $n$ is the number of variables. If the size of the root set $|R|$ is bounded by a constant, the problem becomes polynomial. For bijective CSPs, the number of solutions is exactly equal to the size of the domains after consistency checks, making solution counting trivial.
Conclusion and Future Work
While this work provides a powerful framework for binary functional and bijective constraints, it is currently limited to binary relations and strict semantics. Future research may extend these techniques to $n$-ary constraints and "noisy" or near-functional relations, as well as exploring other semantic classes like monotonic constraints.
Summary updated