Evaluating Search Methods Analytically

Paul Walton Purdom Jr., Cynthia A. BrownAAAI 1982

Abstract

This seminal 1982 paper provides a unified mathematical framework for mapping the "performance geography" of search algorithms. By analyzing average-case complexity on random problems, the authors visualize how problem characteristics—such as clause length and density—determine whether an algorithm achieves polynomial or exponential runtime. The study identifies a central "hard" region in the problem space and demonstrates how specific techniques, like search rearrangement, can significantly expand the boundaries of efficient computation.

Introduction

In the early 1980s, researchers developed various "clever techniques" to accelerate search algorithms for NP-complete problems like Boolean Satisfiability (SAT). However, comparing these methods was difficult due to the lack of a common yardstick. One technique might excel with long clauses, while another performed better with short ones. This paper addresses this fragmentation by creating a unified analytical model to answer a fundamental question: Given the statistical properties of a problem, which algorithm will solve it in polynomial time?

Analytical Framework

The authors employ a Random Conjunctive Normal Form (CNF) model to represent problem instances. These problems are characterized by three parameters:

  • $v$: The number of variables.
  • $t$: The number of clauses.
  • $p$: The probability that a given literal appears in a clause.

By treating $p$ and $t$ as functions of $v$ and analyzing the limit as $v \to \infty$, the authors perform an asymptotic analysis of five primary algorithms: ordinary backtracking, search rearrangement, the pure literal rule, pattern of occurrence analysis, and unused variable elimination. The core innovation is the use of a unified coordinate system ($p(v), t(v)$ space) to plot the boundaries where these algorithms transition from polynomial to exponential average time.

Mapping the Performance Geography

The paper’s most enduring contribution is the visualization of the problem space, mapping out the "territories" where specific algorithms are optimal.

Figure 1: Performance geography of search algorithms, mapping specific problem characteristics to algorithmic efficiency.

Key observations from this mapping include:

  • The "Hard" Hole: A central region exists where none of the analyzed algorithms achieve polynomial time, mathematically defining the "phase transition" where SAT problems become truly difficult.
  • Complementary Strengths: The Pure Literal Rule dominates problems with long clauses ("easy" constraints), while Backtracking serves as the workhorse for "tight" constraints (many short clauses). Unused Variable Elimination is effective for sparse problems where many variables do not impact the outcome.

Quantifying Algorithmic Progress

The analysis provides specific mathematical inequalities for each algorithm's polynomial-time guarantee. For instance, the authors demonstrate that simply changing the evaluation order of variables (search rearrangement) significantly expands the region of solvable problems.

Figure 2: Visualization of the transition between polynomial and exponential regions, highlighting the gains from search rearrangement (Level 1) over fixed backtracking (Level 0).

Figure 2 quantifies the jump in efficiency between "Level 0" (fixed backtracking) and "Level 1" (search rearrangement). The shaded region represents problems that were previously "hard" but became "easy" through better ordering. The authors also identify a "Pseudo-Hard" region where runtime is exponential relative to variables but polynomial relative to the massive input size.

Discussion and Limitations

While the paper provides a powerful visualization tool, it focuses on average-case complexity, meaning algorithms might still face catastrophic outliers. Furthermore, real-world problems often possess internal structures not captured by random CNF models. The authors acknowledge that the key to shrinking the "Hard Problems" territory lies in identifying which elementary techniques to combine into more powerful, general-purpose algorithms. This work remains a foundational step in understanding the boundaries of computational search.

Summary updated

BibTeX
@inproceedings{jr1982evaluating,
  author = {Paul Walton Purdom Jr. and Cynthia A. Brown},
  title = {{Evaluating Search Methods Analytically}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1982},
}
Figure