Phase transitions of PP-complete satisfiability problems
From MaRDI portal
Publication:2643309
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
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