The complexity class PP consists of all decision problems solvable by polynomial-time probabilistic Turing machines. It is well known that PP is a highly intractable complexity class and that PP-complete problems are in all likelihood harder than NP-complete problems. We investigate the existence of phase transitions for a family of PPcomplete Boolean satisfiability problems under the fixed clauses-to-variables ratio model. A typical member of this family is the decision problem #3SAT( ¾ Ò ¾ ): given a 3CNF-formula, is it satisfied by at least the square-root of the total number of possible truth assignments? We provide evidence to the effect that there is a critical ratio Ö ¿ ¾ at which the asymptotic probability of #3SAT( ¾ Ò ¾ ) undergoes a phase transition from 1 to 0. We obtain upper and lower bounds for Ö ¿ ¾
Bailey et al investigate the existence of phase transitions for a family of PP-complete problems-#SAT problems REF .
Phase Transitions of PP-Complete Satisfiability Problems
PROC. 17TH IJCAI-2001
Mathematics Computer Science