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

Sanjeev Arora, Yuval Rabani, Umesh Vazirani

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994
PublisherAssociation for Computing Machinery
Pages459-467
Number of pages9
ISBN (Electronic)0897916638
DOIs
StatePublished - May 23 1994
Externally publishedYes
Event26th Annual ACM Symposium on Theory of Computing, STOC 1994 - Montreal, Canada
Duration: May 23 1994May 25 1994

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
VolumePart F129502
ISSN (Print)0737-8017

Other

Other26th Annual ACM Symposium on Theory of Computing, STOC 1994
CountryCanada
CityMontreal
Period5/23/945/25/94

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Simulating quadratic dynamical systems is PSPACE-complete (preliminary version)'. Together they form a unique fingerprint.

  • Cite this

    Arora, S., Rabani, Y., & Vazirani, U. (1994). Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). In Proceedings of the 26th Annual ACM Symposium on Theory of Computing, STOC 1994 (pp. 459-467). (Proceedings of the Annual ACM Symposium on Theory of Computing; Vol. Part F129502). Association for Computing Machinery. https://doi.org/10.1145/195058.195231