PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS

DOI10.1142/S012905411000774XzbMath1215.68162OpenAlexW2158646537MaRDI QIDQ3069746

Ping Huang, Chunguang Zhou, Junping Zhou, Minghao Yin

Publication date: 19 January 2011

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s012905411000774x

zbMATH Keywords

phase transitionsEXPSPACE-completeconformant planning problemsvariable model

Mathematics Subject Classification ID

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) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (4)

PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP ⋮ An upper (lower) bound for Max (Min) CSP ⋮ Structural attack to anonymous graph of social networks ⋮ Phase transitions of contingent planning problem

Cites Work

• Unnamed Item
• Unnamed Item
• Task decomposition on abstract states, for planning under nondeterminism
• The TSP phase transition
• Approximating the unsatisfiability threshold of random formulas
• Sharp thresholds of graph properties, and the $k$-sat problem
• Random MAX SAT, random MAX CUT, and their phase transitions

This page was built for publication: PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS