Separation of complexity classes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Separation of complexity classes

Full text

Pdf (36 KB)

Source

Journal of the ACM (JACM) archive
Volume 50 , Issue 1 (January 2003) table of contents

Pages: 58 - 62

Year of Publication: 2003

ISSN:0004-5411

Author

Juris Hartmanis

Cornell University

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 91, Citation Count: 0

Additional Information:

references 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/602382.602402 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	Clay Mathematics Institute. 2002. http://www.claymath.org/prizeproblems/index.htm.
	2	Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
	3	Du, D.-Z., and Ko, K. 2000. Theory of Computational Complexity. J. Wiley, New York.
	4	Fagin, R. 1974. Generalized first--order spectra and polynomial-time recognizable sets, in complexity of computations. SIAM-AMS Proc. 7, 27--41.
	5	Immerman, N. 1998. Descriptive Complexity. Springer-Verlag , New York.
	6	Papadimitriou, C. H. 1994. Computational Complexity. Addison-Wesley, Reading, Mass.