Phase transitions of EXPSPACE-complete problems
From MaRDI portal
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Recommendations
- Phase transitions of EXPSPACE-complete problems: a further step
- Phase transitions of contingent planning problem
- Complexity-theoretic models of phase transitions in search problems
- scientific article; zbMATH DE number 67474
- Probabilistic satisfiability: algorithms with the presence and absence of a phase transition
Cites work
- Approximating the unsatisfiability threshold of random formulas
- scientific article; zbMATH DE number 4205985 (Why is no real title available?)
- scientific article; zbMATH DE number 5542185 (Why is no real title available?)
- Random MAX SAT, random MAX CUT, and their phase transitions
- Sharp thresholds of graph properties, and the k-sat problem
- Task decomposition on abstract states, for planning under nondeterminism
- 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: a further step
- 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
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3069746)
