Phase transitions of EXPSPACE-complete problems
DOI10.1142/S012905411000774XzbMATH Open1215.68162OpenAlexW2158646537MaRDI QIDQ3069746FDOQ3069746
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
Recommendations
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Title not available (Why is that?)
- Approximating the unsatisfiability threshold of random formulas
- The TSP phase transition
- Sharp thresholds of graph properties, and the $k$-sat problem
- Task decomposition on abstract states, for planning under nondeterminism
- Random MAX SAT, random MAX CUT, and their phase transitions
- Title not available (Why is that?)
Cited In (8)
- Phase transitions of EXPSPACE-complete problems: a further step
- Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
- Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14--16, 2003
- Structural attack to anonymous graph of social networks
- Phase transitions of contingent planning problem
- An upper (lower) bound for Max (Min) CSP
- Phase Transition for Maximum Not-All-Equal Satisfiability
- Phase transitions of PP-complete satisfiability problems
This page was built for publication: Phase transitions of EXPSPACE-complete problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3069746)
