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

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 18

Satisfiability

The study of phase transitions in algorithmic problems has revealed that usually the critical value of the constrainedness parameter at which the phase transition occurs coincides with the value at which the average cost of natural solvers for the problem peaks. In particular, this confluence of phase transition and peak cost has been observed for the Boolean satisfiability problem and its variants, where the solver used is a Davis-Putnam-type procedure or a suitable modification of it. Here, we investigate the relationship between phase transitions and peak cost for a family of PP-complete satisfiability problems, where the solver used is a symmetric Threshold Counting Davis-Putnam (TCDP) procedure, i.e., a modification of the Counting Davis-Putnman procedure for computing the number of satisfying assignments of a Boolean formula. Our main experimental finding is that, for each of the PP-complete problems considered, the asymptotic probability of solvability undergoes a phase transition at some critical ratio of clauses to variables, but this critical ratio does not always coincide with the ratio at which the average search cost of the symmetric TCDP procedure peaks. Actually, for some of these problems the peak cost occurs at the boundary or even outside of the interval in which the probability of solvability drops from 0.9 to 0.1, and we analyze why this happens.