TY - GEN
T1 - Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)
AU - Arora, Sanjeev
AU - Rabani, Yuval
AU - Vazirani, Umesh
N1 - Publisher Copyright:
© 1994 ACM.
PY - 1994/5/23
Y1 - 1994/5/23
N2 - Quadratic Dynamical Systems (QDS), whose definition extends that of Markov chains, are used to model phenomena in a variety of fields like statistical physics and natural evolution. Such systems also play a role in genetic algorithms, a widelyused class of heuristics that are notoriously hard to analyze. Recently Rabinovich et al. took an important step in the study of QDS'S by showing, under some technical assumptions, that such systems converge to a stationary distribution (similar theorems for Markov Chains are well-known). We show, however, that the following sampling problem for QDS'S is PSPACE-hard: Given an initial distribution, produce a random sample from the t'th generation. The hardness result continues to hold for very restricted classes of QDS'S with very simple initial distributions, thus suggesting that QDS'S are intrinsically more complicated than Markov chains.
AB - Quadratic Dynamical Systems (QDS), whose definition extends that of Markov chains, are used to model phenomena in a variety of fields like statistical physics and natural evolution. Such systems also play a role in genetic algorithms, a widelyused class of heuristics that are notoriously hard to analyze. Recently Rabinovich et al. took an important step in the study of QDS'S by showing, under some technical assumptions, that such systems converge to a stationary distribution (similar theorems for Markov Chains are well-known). We show, however, that the following sampling problem for QDS'S is PSPACE-hard: Given an initial distribution, produce a random sample from the t'th generation. The hardness result continues to hold for very restricted classes of QDS'S with very simple initial distributions, thus suggesting that QDS'S are intrinsically more complicated than Markov chains.
UR - http://www.scopus.com/inward/record.url?scp=0028098410&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0028098410&partnerID=8YFLogxK
U2 - 10.1145/195058.195231
DO - 10.1145/195058.195231
M3 - Conference contribution
AN - SCOPUS:0028098410
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 459
EP - 467
BT - Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PB - Association for Computing Machinery
T2 - 26th Annual ACM Symposium on Theory of Computing, STOC 1994
Y2 - 23 May 1994 through 25 May 1994
ER -