Separating Nondeterministic Time Complexity Classes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Separating Nondeterministic Time Complexity Classes

Full text

Pdf (1.31 MB)

Source

Journal of the ACM (JACM) archive
Volume 25 , Issue 1 (January 1978) table of contents

Pages: 146 - 167

Year of Publication: 1978

ISSN:0004-5411

Authors

Joel I. Seiferas	Computer Science Department, 314 Whitmore Laboratory, The Pennsylvania State University, University Park, PA
Michael J. Fischer	Department of Computer Science, FR-35, University of Washington, Seattle, WA
Albert R. Meyer	Laboratory for Computer Science, NE 43-806, Massachusetts Institute of Technology, Cambridge, MA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 42, Citation Count: 14

Additional Information:

references cited by index terms collaborative colleagues peer to peer

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/322047.322061 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	AANDERAA, S.O On k-tape versus (k - 1)-tape real time computation. In Complexzty of Computatlon (SIAM-AMS Proceedings, Vol 7), R M Karp, Ed, Amer Math. Soc, Providence, R I, 1974, pp 75-96.
	2	Manuel Blum, A Machine-Independent Theory of the Complexity of Recursive Functions, Journal of the ACM (JACM), v.14 n.2, p.322-336, April 1967 [doi>10.1145/321386.321395]
	3	Boor, R V, AND GREmACn, S.A. Quasi-realume languages Math. Syst Theory 4, 2 (June 1970), 97- 111.
	4	BooK, R V., GREmACH, S A, AND WEGBREIT, B. Time- and tape-bounded Tunng acceptors and AFLs. J. Comptr Syst Sci 4, 6 (Dec 1970), 606-621.
	5	Robert L. Constable, The Operator Gap, Journal of the ACM (JACM), v.19 n.1, p.175-183, Jan. 1972 [doi>10.1145/321679.321692]
	6	CONSTABLE, R.L. Two types of Merarchy theorem for axiomatm complexity classes In Computattonal Complexay, R Rustln, Ed., Algonthmics Press, New York, 1973, pp 37-63
	7	COOK, S A. A Merarchy for nondetermimstic time complexity. J Comptr Syst Sct. 7, 4 (Aug. 1973), 343-353
	8	FISCHER, M J , AND RABIN, M.O Super-exponential complexity of Presburger arithmetic In Complexity of Computation (SIAM-AMS Proceedings, Vol. 7), R M Karp, Ed., Amer Math Soc, Providence, R I., 1974, pp 27-41
	9	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]
	10	John Gill , Manuel Blum, On Almost Everywhere Complex Recursive Functions, Journal of the ACM (JACM), v.21 n.3, p.425-435, July 1974 [doi>10.1145/321832.321840]
	11	HARTMAmS, J., AND STEARNS, R.E~ On the computational complextty of algorithms. Trans Amer. Math. Soc 117 (May 1965), 285-306.
	12	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]
	13	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	14	HUNt, H.B III The equivalence problem for regular expressions w~th intersection is not polynomial m tape. Tech Rep. 73-161, Dept. of Comptr Scl., Cornell U, Ithaca, N.Y, March 1973
	15	Oscar H. Ibarra, A Note Concerning Nondeterministic Tape Complexities, Journal of the ACM (JACM), v.19 n.4, p.608-612, Oct. 1972 [doi>10.1145/321724.321727]
	16	IaARgA, O.H On two-way multlhead automata. J Comptr. Syst. Sct 7, 1 (Feb 1973), 28-36.
	17	IaARaX, O H A hierarchy theorem for polynomml-space recognition SlAM j. Comptng 3, 3 (Sept. 1974), 184-187.
	18	LYNCH, N.A., MEYER, A.R., AND FISCHER, M J Relativ~zation of the theory of computational complexity. Trans. Amer Math. Soc 220 (June 1976), 243-287.
	19	MEYER, A.R Weak monadlc second order theory of successor is not elementary-recursive In Logtc Colloqulum, Lecture Notes In Mathematics, No 453, R Parikh, Ed., Springer-Verlag, Berlin, 1975, pp 132-154.
	20	MEYER, A.R, ANt) McCREmHr, E.M Computatlonally complex and pseudo-random zero-one valued functions. In Theory of Machines and Computations, Z. Kohavt and A. Paz, Ed ,Academtc Press, Ne~v York, 1971, pp 19-42.
	21	MEYER, A R., AND STOCKMEYER, L J The equivalence problem for regular expressions with squaring requires exponential space Proc 13th Annual Syrup on Switching and Automata Theory, College Park, Md , 1972, pp 125-129.
	22	W. J. Paul, On time hierarchies, Proceedings of the ninth annual ACM symposium on Theory of computing, p.218-222, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803411]
	23	Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
	24	Run-f, S, AND FISCHER, P C Translational methods and computational complexity Conf. Rec. IEEE Syrup. on Switching Circuit Theory and Logical Design. Ann Arbor, Mich, 1965, pp. 173-178.
	25	J. Seiferas, NONDETERMINISTIC TIME AND SPACE COMPLEXITY CLASSES, Massachusetts Institute of Technology, Cambridge, MA, 1974
	26	SEIFERAS, J.I. Techniques for separating space complexity classes J Comptr. Syst. Sci. 14, 1 (Feb. 1977), 73-99
	27	SEIFEaAS, J I. Relating refined space complexity classes. J Comptr Syst. Sci. 14, 1 (Feb. 1977), 100- 129.
	28	STOCr, MEYER, L.J The complexity of decision problems in automata theory and logic. Tech. Rep. 133, Proj MAC, M I T., Cambridge, Mass., June 1974.
	29	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]
	30	Y^MAD^, H. Real-time computatmn and recurslve functions not real-time computable. IRE Trans. Electron. Comptrs. EC-11, 6 (Dec 1962), 753-760, Correcttons IEEE Trans. Electron, Comptrs. EC- 12, 4 (Aug 1963), 400.
	31	YOUNG, P Easy constructions in complexity theory" Gap and speed-up theorems. Proc. Amer. Math. Soc 37, 2 (Feb. 1973), 555-563.

CITED BY 14

	Pavol Dûriš , Zvi Galil, Two tapes are better than one for nondeterministic machines, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.1-7, May 05-07, 1982, San Francisco, California, United States
	L. Fortnow , M. Sipser, Probabilistic computation and linear time, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.148-156, May 14-17, 1989, Seattle, Washington, United States
	Keith Harrow, How to show something is not: Proofs in formal language and computability theory, ACM SIGCSE Bulletin, v.10 n.3, p.27-30, August 1978
	Dieter van Melkebeek , Ran Raz, A time lower bound for satisfiability, Theoretical Computer Science, v.348 n.2, p.311-320, 8 December 2005
	Dieter Melkebeek , Konstantin Pervyshev, A Generic Time Hierarchy with One Bit of Advice, Computational Complexity, v.16 n.2, p.139-179, May 2007
	Jin-Yi Cai , Ajay Nerurkar , D. Sivakumar, Hardness and hierarchy theorems for probabilistic quasi-polynomial time, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.726-735, May 01-04, 1999, Atlanta, Georgia, United States
	Gillea Brassard, Crusade for a better notation, ACM SIGACT News, v.17 n.1, p.60-64, June 1985
	Viliam Geffert, Space hierarchy theorem revised, Theoretical Computer Science, v.295 n.1-3, p.171-187, 24 February 2003
	Vladimír Glasnak, Sparse sets and collapse of complexity classes, Information and Computation, v.170 n.1, p.26-48, October 10, 2001
	Chris Pollett, Languages to diagonalize against advice classes, Computational Complexity, v.14 n.4, p.341-361, March 2006
	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
	Chuzo Iwamoto , Harumasa Yoneda , Kenichi Morita , Katsunobu Imai, A Recursive Padding Technique on Nondeterministic Cellular Automata, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, v.E91-A n.9, p.2335-2340, September 2008
	Lane A. Hemaspaandra, SIGACT news complexity theory column 52, ACM SIGACT News, v.37 n.3, September 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