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.
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 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