Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)

DOI10.1145/195058.195231zbMath1345.68150OpenAlexW1995326443MaRDI QIDQ2817637

Yuval Rabani, Sanjeev Arora, Umesh V. Vazirani

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195231

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) 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

Complexity of reachability problems for finite discrete dynamical systems ⋮ Membrane computing and complexity theory: A characterization of PSPACE ⋮ Rate of convergence of crossover operators ⋮ Toward a unifying framework for evolutionary processes ⋮ Complexity theory and genetics: The computational power of crossing over