Article

Free access

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

Authors:

Sanjeev Arora,

Yuval Rabani,

Umesh VaziraniAuthors Info & Claims

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

Pages 459 - 467

https://doi.org/10.1145/195058.195231

Published: 23 May 1994 Publication History

PDF eReader

References

[1]

M. AJTAI, J. KOMLOS, AND E. SZE- MERI#DI. Deterministic simulation in LOGSPACE. in Proc. o/the 19th Ann. A CM Syrup. on Theory of Computing, page 132, 1987.

Digital Library

Google Scholar

[2]

L.L. CAVALLI-SFORZA AND W. F. BOD- MER The Genetics of Human Populations W. H. Freeman, San Francisco, 1971.

Google Scholar

[3]

K.L. CLARKSON, D. EPP- STEIN, G.L. MILLER, C. STURTIVANT, AND S.H. TENG. Approximating center points with iterated Radon points. In Proc. o/ the 9th Ann. A CM Syrup. on Computational Geometry, pages 91-98, 1993.

Digital Library

Google Scholar

[4]

M. DYER, A. FRIEZE, AND R. KANNAN. A random polynomial time algorithm for approximating the volume of convex bodies. In Proc. o/the 21st Ann. A CM Syrup. on Theory of Computing, pages 375-381, 1989.

Digital Library

Google Scholar

[5]

M. HIRSCIt AND S. SMALE. Differential Equations, Dynamical Systems, and Linear Algebra. Academic Press, New York, 1974.

Google Scholar

[6]

M. JERRUM AND A. SINCLAIR. Approximating the permanent. SIAM Journal on Computing 18"1149-1178, 1989.

Digital Library

Google Scholar

[7]

M. NAOR. Private communication.

Google Scholar

[8]

A.E. NIX AND M.D. VOSE. Modelling genetic algorithms with Markov chains. In Annals of Mathematics and Artificial Intelligence, vol. 5, pages 79-88, 1992.

Google Scholar

[9]

P. PUDLAK. Private communication.

Google Scholar

[10]

Y. P#ABINOVICtt. Draft of Ph.D. dissertation.

Google Scholar

[11]

Y. RABINOVICH, A. SINCLAIR, AND A. WIGDERSON. Quadratic dynamical systems. In Proc. of the 33rd Ann. IEEE Syrup. on Foudations of Computer Science, pages 304-313, 1992.

Digital Library

Google Scholar

[12]

Y. RABINOVICH AND A. WIGDERSON. Analysis of a simple genetic algorithm. In Proc. of the 4th International Conference on Genetic Algorithms, pages 215- 221, 1991.

Google Scholar

[13]

L.E. REICHL. A Modern Course in Statistical Physics. University of Texas Press, Austin, 1980,

Google Scholar

[14]

L.J. STOCKMEYER AND A.R. MEYER. Word problems requiring exponential time. in Proc. of the 5th Ann. A CM Syrup. on Theory of Computing, pages 1-9, New York, 1973.

Digital Library

Google Scholar

[15]

L.G. VALIENT. Short monotone formulae for the majority function. Journal of Algorithms 5:363-366, 1984.

Crossref

Google Scholar

[16]

M.D. VosE. Modeling simple genetic algorithms. In Foundations of Genetic Algorithms 2, ed. Whitley, Morgan Kaufmann, pages 63-73, 1993.

Google Scholar

Cited By

View all

Caputo PSinclair A(2024)Nonlinear Dynamics for the Ising ModelCommunications in Mathematical Physics10.1007/s00220-024-05129-w405:11Online publication date: 12-Oct-2024
https://doi.org/10.1007/s00220-024-05129-w
Rosenkrantz DVullikanti ARavi SStearns RLevin SPoor HMarathe M(2022)Fundamental limitations on efficiently forecasting certain epidemic measures in network modelsProceedings of the National Academy of Sciences10.1073/pnas.2109228119119:4Online publication date: 19-Jan-2022
https://doi.org/10.1073/pnas.2109228119
Sudholt D(2017)How crossover speeds up building block assembly in genetic algorithmsEvolutionary Computation10.1162/EVCO_a_0017125:2(237-274)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00171
Show More Cited By

Index Terms

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

Recommendations

Robustness of PSPACE-complete sets

We study the robustness of complete languages in PSPACE and prove that they are robust against P-selective sparse sets. Earlier similar results are known for EXP-complete sets [H. Buhrman, A. Hoene, L. Torenvliet, Splittings, robustness, and structure ...
Robust Tracking and Model Following Control with Zero Tracking Error for Uncertain Dynamical Systems

The problem of robust tracking and model following for a class of linear dynamical systems with time-varying uncertain parameters and disturbances is considered. A class of continuous (nonlinear) state feedback controllers is proposed for robust ...
An efficient compact quadratic convex reformulation for general integer quadratic programs

We address the exact solution of general integer quadratic programs with linear constraints. These programs constitute a particular case of mixed-integer quadratic programs for which we introduce in Billionnet et al. (Math. Program., 2010) a general ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing

May 1994

822 pages

ISBN:0897916638

DOI:10.1145/195058

Chairmen:
F. Tom Leighton
Massachusetts Institue of Technology, Cambridge
,
Michael Goodrich
Johns Hopkins Univ., Baltimore, MD

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC94

Sponsor:

SIGACT

STOC94: Symposium on Theory of Computing

May 23 - 25, 1994

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
340
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)3

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Caputo PSinclair A(2024)Nonlinear Dynamics for the Ising ModelCommunications in Mathematical Physics10.1007/s00220-024-05129-w405:11Online publication date: 12-Oct-2024
https://doi.org/10.1007/s00220-024-05129-w
Rosenkrantz DVullikanti ARavi SStearns RLevin SPoor HMarathe M(2022)Fundamental limitations on efficiently forecasting certain epidemic measures in network modelsProceedings of the National Academy of Sciences10.1073/pnas.2109228119119:4Online publication date: 19-Jan-2022
https://doi.org/10.1073/pnas.2109228119
Sudholt D(2017)How crossover speeds up building block assembly in genetic algorithmsEvolutionary Computation10.1162/EVCO_a_0017125:2(237-274)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1162/EVCO_a_00171
Paixão TBadkobeh GBarton NÇörüş DDang DFriedrich TLehre PSudholt DSutton ATrubenová B(2015)Toward a unifying framework for evolutionary processesJournal of Theoretical Biology10.1016/j.jtbi.2015.07.011383(28-43)Online publication date: Oct-2015
https://doi.org/10.1016/j.jtbi.2015.07.011
Motoki T(2010)A new method for modeling the behavior of finite population evolutionary algorithmsEvolutionary Computation10.1162/EVCO_a_0000118:3(451-489)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.1162/EVCO_a_00001
Fischer SRäcke HVöcking BKleinberg J(2006)Fast convergence to Wardrop equilibria by adaptive sampling methodsProceedings of the thirty-eighth annual ACM symposium on Theory of Computing10.1145/1132516.1132608(653-662)Online publication date: 21-May-2006
https://dl.acm.org/doi/10.1145/1132516.1132608
Barrett CHunt HMarathe MRavi SRosenkrantz DStearns R(2006)Complexity of reachability problems for finite discrete dynamical systemsJournal of Computer and System Sciences10.1016/j.jcss.2006.03.00672:8(1317-1345)Online publication date: 1-Dec-2006
https://dl.acm.org/doi/10.1016/j.jcss.2006.03.006
Backofen RClote P(2005)Evolution as a computational engineComputer Science Logic10.1007/BFb0028006(35-55)Online publication date: 15-Jun-2005
https://doi.org/10.1007/BFb0028006
Tošić PAgha G(2005)On computational complexity of counting fixed points in symmetric boolean graph automataProceedings of the 4th international conference on Unconventional Computation10.1007/11560319_18(191-205)Online publication date: 3-Oct-2005
https://dl.acm.org/doi/10.1007/11560319_18
Ollivier Y(2003)Rate of convergence of crossover operatorsRandom Structures & Algorithms10.1002/rsa.1008523:1(58-72)Online publication date: 10-Mar-2003
https://doi.org/10.1002/rsa.10085
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Robustness of PSPACE-complete sets

Robust Tracking and Model Following Control with Zero Tracking Error for Uncertain Dynamical Systems

An efficient compact quadratic convex reformulation for general integer quadratic programs