In 1986, Simon Kasif published a seminal paper that challenged a foundational intuition in the Artificial Intelligence community: the belief that "local" constraint propagation is a natural candidate for massive parallelization. By applying the tools of structural complexity theory to Artificial Intelligence, Kasif demonstrated that discrete relaxation—a fundamental technique for solving Constraint Satisfaction Problems (CSPs)—is inherently sequential.
The Problem: The Allure of Local Constraints
During the mid-1980s, Constraint Satisfaction Problems were at the heart of various AI domains, including computer vision (scene labeling), natural language processing, and automated planning. Given that the general version of a CSP is NP-complete, researchers frequently turned to "discrete relaxation" (also known as network consistency algorithms) to find solutions efficiently.
These algorithms operate by "pruning" labels from objects that violate local constraints. Because these updates occur locally—where a node only needs to check the consistency of its immediate neighbors—the prevailing wisdom suggested that one could achieve near-instantaneous (logarithmic) time by assigning a processor to every node or edge in the network. Kasif’s research sought to determine if this "natural parallel solution" was mathematically feasible or a theoretical impossibility.
Methodology: Proving Sequentiality
To evaluate the parallel potential of these algorithms, Kasif utilized the concept of log-space completeness for P. In complexity theory, a problem is considered "inherently sequential" if it is P-complete. This means that if the problem could be solved in logarithmic time using a polynomial number of processors (the class NC), then every problem in the class P could also be solved in logarithmic time—a scenario considered highly unlikely ($P \neq NC$).
Kasif’s core contribution is a formal reduction. He took a known "hard" sequential problem—the Propositional Horn Clause Satisfiability Problem (PHSP)—and demonstrated a method to transform any instance of PHSP into a Relaxed Consistent Labeling Problem (RCLP) using only logarithmic space. By showing that RCLP can effectively simulate the logic of Horn clauses, Kasif proved that discrete relaxation belongs to the class of P-complete problems.
Key Insights: The "Local Illusion"
The paper’s most profound insight is what might be termed the "Local Illusion." While the operations of a relaxation algorithm are local in nature, the information required to prune a specific label may need to travel across the entire network through a long, serial chain of dependencies.
Kasif leaned on the Parallel Computation Thesis, which suggests that parallel time is related to sequential space. Since discrete relaxation is complete for polynomial time, the pruning process cannot be compressed into logarithmic parallel time without a fundamental revolution in our understanding of complexity classes. Even though discrete relaxation is a form of "incomplete reasoning"—simpler than the full NP-complete CSP—it remains computationally "hard" enough to resist efficient parallelization.
Results and Impact
The paper established several critical results for the field:
- Formal Classification: It successfully classified the Relaxed Consistent Labeling Problem as log-space complete for P.
- Limits of Speedup: The result implies that in the worst-case scenario, a parallel solution is unlikely to provide a polylogarithmic speedup over the best sequential algorithms, such as Mackworth’s linear-time consistency algorithms.
- Strategic Realignment: This shifted the focus of AI research from "massive parallelism" (aiming for log-time results with thousands of processors) toward "controlled parallelism" (aiming for linear speedups with a modest number of processors).
Limitations and Future Directions
Kasif was careful to emphasize that his findings represent a worst-case complexity result. This does not render parallelism useless in practice; rather, it means that a logarithmic time solution cannot be guaranteed for all problem instances.
He suggested that future research should focus on:
- Small-scale Parallelism: Investigating speedups when the number of processors is significantly smaller than the size of the constraint graph.
- Average-case Complexity: Determining if "typical" or "average" instances of CSPs might still be parallelizable, even if the worst-case instances are not.
- Controlled Speedup: Developing algorithms that provide a "full P-processor speedup" (e.g., 10 processors making the task 10x faster) rather than chasing the unattainable goal of logarithmic time.
Summary updated