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

DOI10.1145/195058.195231MaRDI QIDQ2817637zbMATH OpenOpenAlexFDO

Authors Yuval Rabani, Umesh V. Vazirani, Sanjeev Arora

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

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

• scientific article; zbMATH DE number 1256666
• scientific article; zbMATH DE number 1263184
• PSPACE-completeness of majority automata networks
• A computational view of population genetics
• scientific article; zbMATH DE number 1114051

Cited in

(7)

• Complexity theory and genetics: The computational power of crossing over
• scientific article; zbMATH DE number 1256666 (Why is no real title available?)
• scientific article; zbMATH DE number 1341904 (Why is no real title available?)
• Rate of convergence of crossover operators
• Toward a unifying framework for evolutionary processes
• Complexity of reachability problems for finite discrete dynamical systems
• Membrane computing and complexity theory: A characterization of PSPACE

This page was built for publication: Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)

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