PHASE TRANSITIONS OF EXPSPACE-COMPLETE PROBLEMS: A FURTHER STEP

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)

zbMATH Keywords

upper boundphase transitionlower boundconformant planningconformant plan modificationEXPSPACE-complete

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)

Related Items (4)

An upper (lower) bound for Max (Min) CSP ⋮ Structural attack to anonymous graph of social networks ⋮ Phase transitions of contingent planning problem ⋮ Phase Transition for Maximum Not-All-Equal Satisfiability

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

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