PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP
From MaRDI portal
Publication:2909190
DOI10.1142/S0129054112500025zbMath1246.68206MaRDI QIDQ2909190
Jinyan Wang, Minghao Yin, Junping Zhou, Xiangtao Li
Publication date: 30 August 2012
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
upper bound; phase transition; lower bound; conformant planning; conformant plan modification; EXPSPACE-complete
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Phase Transition for Maximum Not-All-Equal Satisfiability, Structural attack to anonymous graph of social networks, Phase transitions of contingent planning problem, An upper (lower) bound for Max (Min) CSP
Cites Work
- Unnamed Item
- Random constraint satisfaction: easy generation of hard (satisfiable) instances
- The TSP phase transition
- Many hard examples in exact phase transitions
- Phase transitions of PP-complete satisfiability problems
- PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS
- Critical Behavior in the Satisfiability of Random Boolean Expressions
- Random MAX SAT, random MAX CUT, and their phase transitions