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

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

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

Full text

Pdf (752 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 459 - 467

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Sanjeev Arora	UC Berkeley
Yuval Rabani	MIT
Umesh Vazirani	UC Berkeley

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 13, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195231 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	AKS	M. Ajtai , J. Komlos , E. Szemeredi, Deterministic simulation in LOGSPACE, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.132-140, January 1987, New York, New York, United States [doi>10.1145/28395.28410]
	CB	L.L. CAVALLI-SFORZA AND W. F. BOD- MER The Genetics of Human Populations W. H. Freeman, San Francisco, 1971.
	CEMST	K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161004]
	DFK	M. Dyer , A. Frieze, A random polynomial time algorithm for approximating the volume of convex bodies, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.375-381, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73043]
	HS	M. HIRSCIt AND S. SMALE. Differential Equations, Dynamical Systems, and Linear Algebra. Academic Press, New York, 1974.
	JS	M. Jerrum , Alistair Sinclair, Approximating the permanent, SIAM Journal on Computing, v.18 n.6, p.1149-1178, Dec. 1989 [doi>10.1137/0218077]
	Nao	M. NAOR. Private communication.
	NV	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.
	Pud	P. PUDLAK. Private communication.
	Rab	Y. P#ABINOVICtt. Draft of Ph.D. dissertation.
	RSW	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.
	RW	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.
	Rei	L.E. REICHL. A Modern Course in Statistical Physics. University of Texas Press, Austin, 1980,
	SM	L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
	Val	L.G. VALIENT. Short monotone formulae for the majority function. Journal of Algorithms 5:363-366, 1984.
	Vos	M.D. VosE. Modeling simple genetic algorithms. In Foundations of Genetic Algorithms 2, ed. Whitley, Morgan Kaufmann, pages 63-73, 1993.

CITED BY 6

	Yuval Rabani , Yuri Rabinovich , Alistair Sinclair, A computational view of population genetics, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.83-92, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Yann Ollivier, Rate of convergence of crossover operators, Random Structures & Algorithms, v.23 n.1, p.58-72, August 2003
	P. Pudlák, Complexity theory and genetics: the compuational power of crossing over, Information and Computation, v.171 n.2, p.201-223, December 15, 2001
	Christopher L. Barrett , Harry B. Hunt, III , Madhav V. Marathe , S. S. Ravi , Daniel J. Rosenkrantz , Richard E. Stearns, Complexity of reachability problems for finite discrete dynamical systems, Journal of Computer and System Sciences, v.72 n.8, p.1317-1345, December, 2006
	Simon Fischer , Harald Räcke , Berthold Vöcking, Fast convergence to Wardrop equilibria by adaptive sampling methods, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Petr Sosík , Alfonso Rodríguez-Patón, Membrane computing and complexity theory: A characterization of PSPACE, Journal of Computer and System Sciences, v.73 n.1, p.137-152, February, 2007