Beyond NP: The QSAT Phase Transition

Abstract

We show that phase transition behaviour similar to that observed in NP-complete problems like random 3-Sat occurs in Pspace-complete 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 to us from Sat and other NP-complete domains. There do, however, appear to be some slight differences. When problems contain short clauses, there is a large gap between worst case behaviour and median, and the easy-hard-easy pattern is restricted to the higher percentiles of the search cost. In addition, our theory of constrainedness appears to be rather less accurate at predicting the precise location of the phase transition compared to many NP-complete problems. We conjecture that the accuracy may be influenced by the super-exponential size of...