Phase transitions of EXPSPACE-complete problems: a further step

DOI10.1142/S0129054112500025MaRDI QIDQ2909190zbMATH OpenFDO

Authors Junping Zhou, Minghao Yin, Xiangtao Li, Jinyan Wang

Publication date 30 August 2012

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

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

zbMATH Keywords

conformant plan modificationconformant planningEXPSPACE-completelower boundphase transitionupper bound

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Recommendations

• Phase transitions of EXPSPACE-complete problems
• Phase transitions of contingent planning problem
• Random 3-SAT: The plot thickens
• Complexity-theoretic models of phase transitions in search problems
• Phase Transition for Maximum Not-All-Equal Satisfiability

Cites work

• Critical Behavior in the Satisfiability of Random Boolean Expressions
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• Many hard examples in exact phase transitions
• Phase transitions of EXPSPACE-complete problems
• Phase transitions of PP-complete satisfiability problems
• Random constraint satisfaction: easy generation of hard (satisfiable) instances
• Random MAX SAT, random MAX CUT, and their phase transitions
• The TSP phase transition

Cited in

(8)

• Phase transitions of PP-complete satisfiability problems
• Epsilon-transformation: exploiting phase transitions to solve combinatorial optimization problems
• Phase transitions of EXPSPACE-complete problems
• Structural attack to anonymous graph of social networks
• Phase Transition for Maximum Not-All-Equal Satisfiability
• Phase transitions of contingent planning problem
• Typical case complexity and phase transitions. Papers from the workshop, Ottawa, ON, Canada, May 14--16, 2003
• An upper (lower) bound for Max (Min) CSP

This page was built for publication: Phase transitions of EXPSPACE-complete problems: a further step

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909190)