Phase transitions of PP-complete satisfiability problems

DOI10.1016/j.dam.2006.09.014zbMath1123.68117OpenAlexW2068660261MaRDI QIDQ2643309

Delbert D. Bailey, Phokion G. Kolaitis, Victor Dalmau

Publication date: 23 August 2007

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/10230/36324

zbMATH Keywords

phase transitionssatisfiabilityPP-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP ⋮ The effect of combination functions on the complexity of relational Bayesian networks ⋮ The complexity of Bayesian networks specified by propositional and relational languages

Cites Work

• The complexity of computing the permanent
• A threshold for unsatisfiability
• On counting problems and the polynomial-time hierarchy
• The computational complexity of propositional STRIPS planning
• Differential equations for random processes and random graphs
• Dempster's rule of combination is {\#}P-complete
• Generating hard satisfiability problems
• A probabilistic analysis of propositional STRIPS planning
• On the hardness of approximate reasoning
• Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract)
• Probabilistic Analysis of Two Heuristics for the 3-Satisfiability Problem
• The Complexity of Enumeration and Reliability Problems
• Computational Complexity of Probabilistic Turing Machines
• Stochastic Boolean satisfiability
• Lower bounds for random 3-SAT via differential equations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item