Phase transitions of PP-complete satisfiability problems
Mostra el registre complet Registre parcial de l'ítem
- dc.contributor.author Bailey, Delbert D.
- dc.contributor.author Dalmau, Víctor
- dc.contributor.author Kolaitis, Phokion G.
- dc.date.accessioned 2019-01-18T09:09:17Z
- dc.date.available 2019-01-18T09:09:17Z
- dc.date.issued 2007
- dc.description.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: 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 by showing that . We also carry out a set of experiments on random instances of # 3SAT using a natural modification of the Davis–Putnam–Logemann–Loveland (DPLL) procedure. Our experimental results suggest that . Moreover, the average number of recursive calls of this modified DPLL procedure reaches a peak around 2.5 as well.en
- dc.format.mimetype application/pdf
- dc.identifier.citation Bailey DD, Dalmau V, Kolaitis PG. Phase transitions of PP-complete satisfiability problems. Discrete Appl Math. 2007 Jun 15;155(12):1627-39. DOI: 10.1016/j.dam.2006.09.014
- dc.identifier.doi http://dx.doi.org/10.1016/j.dam.2006.09.014
- dc.identifier.issn 0166-218X
- dc.identifier.uri http://hdl.handle.net/10230/36324
- dc.language.iso eng
- dc.publisher Elsevier
- dc.relation.ispartof Discrete Applied Mathematics. 2007 Jun 15;155(12):1627-39.
- dc.rights © Elsevier http://dx.doi.org/10.1016/j.dam.2006.09.014
- dc.rights.accessRights info:eu-repo/semantics/openAccess
- dc.subject.keyword Phase transitions
- dc.subject.keyword Satisfiability
- dc.subject.keyword PP-complete
- dc.title Phase transitions of PP-complete satisfiability problems
- dc.type info:eu-repo/semantics/article
- dc.type.version info:eu-repo/semantics/acceptedVersion