Summary: 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 PP-complete Boolean satisfiability problems under the fixed clauses-to-variables ratio model. A typical member of this family is the decision problem \(\#3\text{Sat}(\geq 2^{n/2})\): 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 \(r_{3,2}\) at which the asymptotic probability of \(\#3\text{Sat}(\geq 2^{n/2})\) undergoes a phase transition from 1 to 0. We obtain upper and lower bounds for \(r_{3,2}\) by showing that \(0.9227 \leq r_{3,2} \leq 2.595\). We also carry out a set of experiments on random instances of \(\#3 \text{Sat}( \geq 2^{n/2})\) using a natural modification of the Davis-Putnam-Logemann-Loveland (DPLL) procedure. Our experimental results suggest that \(r_{3,2}\sim 2.5\). Moreover, the average number of recursive calls of this modified DPLL procedure reaches a peak around 2.5 as well.
For the entire collection see [Zbl 0968.90001].