Relations Among Complexity Measures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Relations Among Complexity Measures

Full text

Pdf (1.51 MB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 2 (April 1979) table of contents

Pages: 361 - 381

Year of Publication: 1979

ISSN:0004-5411

Authors

Nicholas Pippenger	Mathematical Sciences Department, P O Box 218, IBM Thomas J Watson Research Center, Yorktown Heights, NY
Michael J. Fischer	Department of Computer Science, University of Washington, Seattle, WA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 72, Citation Count: 32

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/322123.322138 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.

	1	COOK, S A, AND AANDERAA, S O On the minimum computation time of functions Trans AMS 142 (Aug 1969), 291-314
	2	Patrick C. Fischer , Albert R. Meyer , Arnold L. Rosenberg, Real-Time Simulation of Multihead Tape Units, Journal of the ACM (JACM), v.19 n.4, p.590-607, Oct. 1972 [doi>10.1145/321724.321726]
	3	HENNIE, F C On-line Turlng machine computations IEEE Trans EC 15, 1 (Feb 1966), 34--44
	4	F. C. Hennie , R. E. Stearns, Two-Tape Simulation of Multitape Turing Machines, Journal of the ACM (JACM), v.13 n.4, p.533-546, Oct. 1966 [doi>10.1145/321356.321362]
	5	Benton Leong , Joel Seiferas, New real-time simulations of multihead tape units, Proceedings of the ninth annual ACM symposium on Theory of computing, p.239-248, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803414]
	6	MULLER, D E Complexity tn electromc swltchmg circuits IRE Tram EC 5, 1 (March 1956), 15-19
	7	PATERSON, M S, FISCHER, M J, AND MEYER, A R An improved overlap argument for on-hne mult~phcatlon SIA M-A MS Proc 7 (1974), 97-111
	8	J. E. Savage, Computational Work and Time on Finite Machines, Journal of the ACM (JACM), v.19 n.4, p.660-674, Oct. 1972 [doi>10.1145/321724.321731]
	9	SCHNORR, C P The network complextty and the Turmg machine complextty of fimte funcUons Acta Informatlca 7 (1976), 95-107
	10	STOSS, H-J Zwel-band Simulation von Turmgmaschmen Computing 7 (1971), 222-235
	11	TURING, A M On computable numbers, wRh an apphcatlon to the Entschetdungsproblem Proc London Math Soc (2) 42 (1936), 230-265, correcttons 43 (1937), 544-546

CITED BY 32

	Jordi Fernández, Explanation by Computer Simulation in Cognitive Science, Minds and Machines, v.13 n.2, p.269-284, May 2003
	O. Goldreich, Towards a theory of software protection and simulation by oblivious RAMs, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.182-194, January 1987, New York, New York, United States
	Viggo Kann, Polynomially bounded minimization problems that are hard to approximate, Nordic Journal of Computing, v.1 n.3, p.317-331, Fall 1994
	Oded Goldreich , Rafail Ostrovsky, Software protection and simulation on oblivious RAMs, Journal of the ACM (JACM), v.43 n.3, p.431-473, May 1996
	Dale Myers, The random access hierarchy, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.355-364, December 1983
	Wolfgang J. Paul , Joel I. Seiferas , Janos Simon, An information-theoretic approach to time bounds for on-line computation (preliminary version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.357-367, April 28-30, 1980, Los Angeles, California, United States
	Arnold L. Rosenberg, Encoding Data Structures in Trees, Journal of the ACM (JACM), v.26 n.4, p.668-689, Oct. 1979
	Paul M.B. Vitányi, Real-time simulation of multicounters by oblivious one-tape turing machines (Preliminary Draft), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.27-36, May 05-07, 1982, San Francisco, California, United States
	Michael Kaminski, A linear time algorithm for residue computation and a fast algorithm for division with a sparse divisor, Journal of the ACM (JACM), v.34 n.4, p.968-984, Oct. 1987
	Burkhard Monien , Ivan Hal Sudborough, Bandwidth constrained NP-Complete problems, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.207-217, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Nicholas Pippenger, Probabilistic simulations (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.17-26, May 05-07, 1982, San Francisco, California, United States
	Joel I. Seiferas , Paul M. B. Vitányi, Counting is easy, Journal of the ACM (JACM), v.35 n.4, p.985-1000, Oct. 1988
	Stephen A. Cook, An overview of computational complexity, Communications of the ACM, v.26 n.6, p.400-408, June 1983
	Marco Carpentieri, On the simulation of quantum Turing machines, Theoretical Computer Science, v.304 n.1-3, p.103-128, 28 July 2003
	Nicholas Pippenger , Leslie G. Valiant, Shifting Graphs and Their Applications, Journal of the ACM (JACM), v.23 n.3, p.423-432, July 1976
	Larry Stockmeyer , Albert R. Meyer, Cosmological lower bound on the circuit complexity of a small problem in logic, Journal of the ACM (JACM), v.49 n.6, p.753-784, November 2002
	Markus Holzer, Multi-head finite automata: data-independent versus data-dependent computations, Theoretical Computer Science, v.286 n.1, p.97-116, 6 September 2002
	Sergio De Agostino , Riccardo Silvestri, Bounded size dictionary compression: SC^k -completeness and NC algorithms, Information and Computation, v.180 n.2, p.101-112, 29 January 2003
	Michael Wooldridge , Paul E. Dunne, On the computational complexity of qualitative coalitional games, Artificial Intelligence, v.158 n.1, p.27-73, September 2004
	Krishna V. Palem, Energy Aware Computing through Probabilistic Switching: A Study of Limits, IEEE Transactions on Computers, v.54 n.9, p.1123-1137, September 2005
	Paul E. Dunne , Michael Wooldridge , Michael Laurence, The complexity of contract negotiation, Artificial Intelligence, v.164 n.1-2, p.23-46, May 2005
	Lance Fortnow , Richard Lipton , Dieter van Melkebeek , Anastasios Viglas, Time-space lower bounds for satisfiability, Journal of the ACM (JACM), v.52 n.6, p.835-865, November 2005
	Micah Adler , Nicholas J. A. Harvey , Kamal Jain , Robert Kleinberg , April Rasala Lehman, On the capacity of information networks, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.241-250, January 22-26, 2006, Miami, Florida
	Lvzhou Li , Daowen Qiu, Determination of equivalence between quantum sequential machines, Theoretical Computer Science, v.358 n.1, p.65-74, 31 July 2006
	Guy Wolfovitz, The complexity of depth-3 circuits computing symmetric Boolean functions, Information Processing Letters, v.100 n.2, p.41-46, 31 October 2006
	Dieter van Melkebeek, A survey of lower bounds for satisfiability and related problems, Foundations and Trends in Theoretical Computer Science, v.2 n.3, p.197-303, January 2006
	Ryan Williams, Inductive Time-Space Lower Bounds for Sat and Related Problems, Computational Complexity, v.15 n.4, p.433-470, December 2006
	Kenneth W. Regan, Machine models and linear time complexity, ACM SIGACT News, v.24 n.3, p.5-15, Oct. 1993
	R. Ostrovsky, Efficient computation on oblivious RAMs, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.514-523, May 13-17, 1990, Baltimore, Maryland, United States
	Paul E. Dunne , Yann Chevaleyre, The complexity of deciding reachability properties of distributed negotiation schemes, Theoretical Computer Science, v.396 n.1-3, p.113-144, May, 2008
	Stephen A. Cook, An overview of computational complexity, ACM Turing award lectures, ACM, New York, NY, 2007
	Eric B. Baum, Review:, Neural Computation, v.1 n.2, p.201-207, Summer 1989