Comparing Phase Transitions and Peak Cost in PP-Complete Satisfiability Problems

AAAI 2002

TL;DR

This paper investigates the relationship between phase transitions (where problem solvability sharply drops) and peak computational cost for a class of "hard" PP-complete satisfiability problems. Surprisingly, they find that the peak cost for their solver doesn't always align with the phase transition, challenging a long-held conjecture in the field.

What Problem Does This Paper Address?

For decades, researchers have observed a fascinating phenomenon in computationally hard problems: as a "constrainedness" parameter (like the ratio of clauses to variables in a logic puzzle) increases, the probability of a random instance being solvable often drops dramatically over a very narrow range. This is called a "phase transition." Intriguingly, this transition point often coincides with the point where the average computational cost of solving these problems peaks. This has led to a conjecture that the average cost of any reasonable solver for a problem will peak around its phase transition.

However, recent work has shown this isn't always true, especially for solvers with different underlying mechanisms. This paper focuses on a specific class of problems called PP-complete satisfiability problems, which are considered even harder than NP-complete problems. They use a specialized solver and aim to see if the phase transition and peak cost still align for these challenging problems.

Methods

The authors employ a modified version of the Counting Davis-Putnam (CDP) procedure, called the symmetric Threshold Counting Davis-Putnam (TCDP) procedure. This algorithm is designed to count the number of satisfying assignments for Boolean formulas. The "symmetric" aspect means it maintains both an upper and a lower bound on the count of satisfying assignments, allowing for earlier termination if the target threshold is met or deemed unreachable.

They apply this TCDP solver to a family of PP-complete problems known as #3SAT(> 2^an), where a is a parameter controlling the threshold for the number of satisfying assignments. The core of their method involves:

  1. Generating random instances: Creating large numbers of random 3-CNF formulas for varying numbers of variables (n) and clause-to-variable ratios (r).
  2. Measuring solvability: Determining the probability that a randomly generated formula has at least 2^an satisfying assignments for a given r and n. This allows them to identify the phase transition point r*(a).
  3. Measuring computational cost: Recording the number of recursive calls made by the TCDP solver to determine if an instance meets the threshold. This allows them to find the peak average search cost.
  4. Comparing transition and peak: Analyzing how the r*(a) (phase transition point) relates to the r value where the average cost peaks, for different values of a.

Datasets

The paper does not introduce new datasets. Instead, they generate random 3-CNF formulas with varying numbers of variables (10, 20, 30, and 40) and clause-to-variable ratios. These generated instances serve as their experimental "dataset" for evaluating both the phase transition behavior and the solver's performance.

Key Insights and Ideas

  • Challenging the Confluence: The most significant finding is that for certain PP-complete problems, the peak computational cost of the TCDP solver does not always coincide with the phase transition point. This directly challenges the previously observed correlation and suggests that peak cost can be solver-dependent, even for sophisticated algorithms.
  • Peak Cost Shift: For higher values of the parameter a (meaning a higher threshold for satisfying assignments), the peak cost shifts significantly to the right of the phase transition window. In some cases, it occurs even outside the interval where the probability of solvability drops from 0.9 to 0.1.
  • Solver Behavior: The paper provides a qualitative analysis explaining why this mismatch occurs, relating it to how the TCDP solver terminates early when it can determine the threshold is met or not met, and how this interacts with the problem's structure at different constraint levels.
  • Analytical Bounds vs. Experiment: The experimental results also highlight the effectiveness of analytical bounds (like those derived from Markov's inequality) for estimating phase transition points, showing they become progressively tighter for the PP-complete problems studied as a increases.

Key Results

  • For the family of PP-complete problems #3SAT(> 2^an), a phase transition in the probability of solvability was observed at a critical ratio r*(a) of clauses to variables.
  • For a <= 0.7, the peak average search cost of the symmetric TCDP procedure occurred at or near the phase transition ratio r*(a).
  • For a = 0.8 and a = 0.9, the peak cost occurred at r = 1.2, which was at the boundary or significantly to the right of the phase transition window (e.g., for a = 0.9, the transition window was [0.475, 0.575]).
  • The average search cost of the TCDP solver generally increases with the parameter a.
  • The peak cost for a = 0.8 and a = 0.9 coincided with the peak cost ratio observed for the basic CDP procedure on #SAT problems, suggesting a connection between the difficulty of PP-complete and #P-complete problems.

Limitations and Future Work

  • Analytical Proof of Phase Transition: While the experiments strongly suggest phase transitions exist for these PP-complete problems, a formal analytical proof remains an open problem.
  • Generalizability of TCDP: The study focuses on a specific TCDP solver. Further research could explore whether other solvers for these PP-complete problems exhibit similar behavior.
  • Quantitative Analysis of Peak Shift: While a qualitative explanation for the peak cost shift is provided, a more rigorous quantitative analysis could be beneficial.
  • Other PP-Complete Problems: The study focuses on a specific family of PP-complete problems. Investigating other types of PP-complete problems would provide a broader understanding.
  • Median vs. Average Cost: While the paper notes that median cost behaves similarly to average cost in their experiments, a deeper dive into the differences between these measures for these problems could be interesting.

Summary updated

BibTeX
@inproceedings{2002comparing,
  title = {{Comparing Phase Transitions and Peak Cost in PP-Complete Satisfiability Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2002},
}
Figure