Beyond NP: The QSAT Phase Transition

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Satisfiability

We show that phase transition behaviour similar to that observed in NP-complete problems like random 3-SAT occurs in PSPACEcomplete problems like random QSAT. Most of the differences in phase transition behaviour that Cadoli et al report for random QSAT problems (for instance, no fixed point and no easy-hard-easy pattern) are largely due to the presence of trivially unsatisfiable problems. Once they are removed, we see behaviour more familiar from SAT and other NP-complete domains. There are, however, some differences. Problems with short clauses show a large gap between worst case behaviour and median, and the easy-hard-easy pattern is restricted to higher percentiles of search cost. We compute the "constrainedness" of QSAT problems, and use this to predict the location of phase transitions. We conjecture that these predictions are less accurate than in NP-complete problems because of the super-exponential size of the state space, and of the weakness of first moment methods in complexity classes above NP. Finally, we predict that similar phase transition behaviour will occur in other PSPACE-complete problems like planning and game playing.