On Reducibility to Complex or Sparse Sets

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On Reducibility to Complex or Sparse Sets

Full text

Pdf (330 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 3 (July 1975) table of contents

Pages: 341 - 345

Year of Publication: 1975

ISSN:0004-5411

Author

Nancy Lynch

Department of Mathematics, University of Southern California, University Park, Los Angeles, CA

Publisher

ACM New York, NY, USA

Bibliometrics

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

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/321892.321895 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	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]
	2	KAnP, R. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85-103.
	3	LYNCH, N. Complexity-class encoding sets. Submitted fer publication.
	4	LYNCH, N. Helping: Several formalizations. J. Symbolic Logic (to appear).
	5	LYNch, N., MEYEn, A., AND FmcnEn, M. Relativization of the theory of computational complexity. Trans. AMS (to appear).
	6	A. R. Meyer, WEAK MONADIC SECOND ORDER THEORY OF SUCCESSOR IS NOT ELEMENTARY-RECURSIVE, Massachusetts Institute of Technology, Cambridge, MA, 1973
	7	STOCKMEYEn, L. Ph.D. Th., Dep. of Elec. Eng., M.I.T., Cambridge, Mass., June 1974.
	8	SOLOVAY, R. Private communication.

CITED BY 5

	Istvan Simon , John Gill, Polynomial reducibilities and upward diagonalizations, Proceedings of the ninth annual ACM symposium on Theory of computing, p.186-194, May 04-04, 1977, Boulder, Colorado, United States
	Pekka Orponen , Ker-i Ko , Uwe Schöning , Osamu Watanabe, Instance complexity, Journal of the ACM (JACM), v.41 n.1, p.96-121, Jan. 1994
	Ronald V. Book , Ding-Zhu Du, The existence and density of generalized complexity cores, Journal of the ACM (JACM), v.34 n.3, p.718-730, July 1987
	Shimon Even , Alan L. Selmen , Yacov Yacobi, Hard-core theorems for complexity classes, Journal of the ACM (JACM), v.32 n.1, p.205-217, Jan. 1985
	Tomoyuki Yamakami , Toshio Suzuki, Resource bounded immunity and simplicity, Theoretical Computer Science, v.347 n.1-2, p.90-129, 30 November 2005