Using Deep Structure to Locate Hard Problems

Colin P. Williams, Tad HoggAAAI 1992

Introduction

In the early 1990s, AI researchers encountered a puzzling phenomenon: while most instances of NP-complete problems like graph coloring were computationally "easy," a small subset proved incredibly difficult. While theoretical work could predict these abrupt changes in cost for naive algorithms, it struggled to explain why sophisticated, "smart" algorithms also hit these performance walls. This foundational 1992 paper from Xerox PARC shifts the focus from specific algorithmic implementations to the "deep structure" of the problem's search space to predict where these hard instances lie.

Modeling the Search Space

The authors introduce a method to analyze problem difficulty by modeling the search space as a directed lattice of "assumptions" (variable/value pairings).

The search space of a Constraint Satisfaction Problem modeled as a lattice of assumptions.

By characterizing problems using "minimized nogoods"—the smallest sets of assignments that violate a constraint—the authors define an algorithm-independent cost ($C_s$) based on the number of "goods" (partial solutions) within the lattice. They argue that a sophisticated algorithm's primary effect is to prune a fixed fraction of the redundant search space, meaning the underlying structural difficulty remains a property of the lattice itself.

The Phase Transition and the "Bulge" Effect

Using a "mean field approximation" borrowed from statistical mechanics, the authors derived formulas to estimate the expected number of solutions and the probability of a solution's existence. Their analysis revealed that hardness is non-linear, driven by a structural phase transition.

At a critical value ($\beta_{crit}$), a problem transitions from having exponentially many solutions to having almost none. The "hardest" problems occur exactly at this boundary. This is caused by the "bulge" effect: at the transition, there are very few full solutions at the top of the search lattice, but many "partial solutions" lower down. These partial solutions act as sirens, luring search algorithms into deep, fruitless branches of the search tree.

Empirical Results and Validation

The paper validates its theoretical framework using the Graph Coloring Problem, comparing predictions against experimental data for graphs with 81 and 144 nodes.

Comparison of theoretical predictions and experimental results for critical connectivity.

The theoretical estimates for the critical connectivity were remarkably accurate, falling within 15% of experimental results. Furthermore, the model predicted that increasing from 3 to 4 colors would shift the "hard zone" by a factor of 1.73; experimental data showed a shift of 1.70—a mere 2% error. The authors also confirmed that variance in problem difficulty peaks during the phase transition, explaining why random instances in this zone can vary so wildly in complexity.

Conclusion

By identifying the structural drivers of computational hardness, this research provides a quantitative way to locate the "hard zone" of CSPs. While the current model assumes constraint independence—a simplification that may not hold in complex real-world problems—it offers a powerful predictive tool. One practical takeaway is that preprocessing strategies are most effective right at the phase transition, suggesting that structural awareness can directly inform more efficient search strategies.

Summary updated

BibTeX
@inproceedings{williams1992using,
  author = {Colin P. Williams and Tad Hogg},
  title = {{Using Deep Structure to Locate Hard Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure