Presented at AAAI-82, Bernard Nudel’s work represents a foundational step in understanding the computational complexity of Constraint Satisfaction Problems (CSPs). By moving beyond simple uniform probability models, Nudel introduced analytical theories that predict the performance of search algorithms like Forward Checking (FC) before execution begins. This allows for the selection of optimal variable orderings, potentially saving massive amounts of computation time in NP-complete tasks.
The Challenge of Variable Ordering
Consistent-Labeling Problems (CLPs), now more commonly known as CSPs, underpin diverse fields such as graph coloring, scheduling, and computer vision. While algorithms like Backtracking and Forward Checking are standard tools for solving them, their efficiency is notoriously sensitive to variable ordering. Selecting the wrong variable to instantiate first can lead to an exponential explosion in the search tree.
Previous theoretical work (notably by Haralick) relied on "Level-0" theories, which assumed a uniform probability of compatibility between all variable pairs. Nudel’s research aims to bridge the gap between these abstract models and the non-uniform reality of specific problem instances.
A Hierarchy of Predictive Theories
Nudel developed a hierarchy of theories to estimate algorithmic complexity based on the structure of the problem:
- c-classes and cc-matrices: Problems are grouped into "compatibility classes" based on their compatibility-count (cc) matrix, which tracks the number of allowed value pairs between any two variables $i$ and $j$.
- Level-1 Theory: This theory utilizes a matrix of probabilities $[p_{ij}]$ derived from the specific compatibility ratios of the problem, rather than a single global probability.
- Level-2 Theory: A more refined version providing exact averages for a given c-class, though it is more analytically complex than Level-1.
Key Insights: Shadowing and Homogeneity
One of the most practical findings is the "Shadowing" Effect. Even when the simpler Level-1 theory slightly underestimates the total number of consistency checks, it tracks the peaks and troughs of the more complex Level-2 theory almost perfectly. This makes it an excellent, computationally cheaper tool for ranking different variable orderings.
Furthermore, Nudel discovered a high degree of Homogeneity within Classes. As seen in Figure 1, the spread of complexity within a single c-class is remarkably small, with standard deviations often between 5–10%. This justifies using the class average as a highly accurate proxy for an individual problem's performance.
Predictive Power in Benchmarks
The theories were validated using the classic 5-Queens problem. By testing 60 different variable permutations, Nudel demonstrated that the theoretical models could identify the most efficient search paths.
As illustrated in Figure 2, the number of consistency checks can fluctuate wildly (e.g., from 200 to 300) just by changing the variable order. The Level-1 and Level-2 theories successfully predict these fluctuations, whereas the older Level-0 theory (represented by the flat line) provides no guidance on ordering.
Conclusion and Future Directions
Nudel’s work confirms that theoretical estimates for nodes and checks are typically within 5–10% of experimental results. While the current framework focuses on binary constraints and static global orderings, it lays the groundwork for "inverting" the theory—creating formulas that directly output the optimal ordering from the cc-matrix without testing permutations. Future extensions may apply these theories locally at every node in the search tree to enable highly efficient dynamic variable ordering.
Summary updated