ML Anthology

Phase Transitions of PP-Complete Satisfiability Problems

Delbert D. Bailey, Víctor Dalmau, Phokion G. Kolaitis
IJCAI 2001 pp. 183-192
doi:10.1016/j.dam.2006.09.014 /ijcai/2001/bailey2001ijcai-phase/

Abstract

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 # 3SAT ( ⩾ 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 # 3SAT ( ⩾ 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 ⩽ r 3 , 2 ⩽ 2.595 . We also carry out a set of experiments on random instances of # 3SAT ( ⩾ 2 n / 2 ) using a natural modification of the Davis–Putnam–Logemann–Loveland (DPLL) procedure. Our experimental results suggest that r 3 , 2 ≈ 2.5 . Moreover, the average number of recursive calls of this modified DPLL procedure reaches a peak around 2.5 as well.

PDF IJCAI Semantic Scholar

Cite

Text

Bailey et al. "Phase Transitions of PP-Complete Satisfiability Problems." International Joint Conference on Artificial Intelligence, 2001. doi:10.1016/j.dam.2006.09.014

Markdown

[Bailey et al. "Phase Transitions of PP-Complete Satisfiability Problems." International Joint Conference on Artificial Intelligence, 2001.](https://mlanthology.org/ijcai/2001/bailey2001ijcai-phase/) doi:10.1016/j.dam.2006.09.014

BibTeX

@inproceedings{bailey2001ijcai-phase,
  title     = {{Phase Transitions of PP-Complete Satisfiability Problems}},
  author    = {Bailey, Delbert D. and Dalmau, Víctor and Kolaitis, Phokion G.},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2001},
  pages     = {183-192},
  doi       = {10.1016/j.dam.2006.09.014},
  url       = {https://mlanthology.org/ijcai/2001/bailey2001ijcai-phase/}
}