How reductions to sparse sets collapse the polynomial-time hierarchy: a primer

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

How reductions to sparse sets collapse the polynomial-time hierarchy: a primer: Part II restricted polynomial-time reductions

Full text

Pdf (768 KB)

Source

ACM SIGACT News archive
Volume 23 , Issue 4 (Fall 1992) table of contents

Pages: 83 - 94

Year of Publication: 1992

ISSN:0163-5700

Author

Paul Young

Publisher

ACM New York, NY, USA

Bibliometrics

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

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	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/148080.148084 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	[BBJSY-89] Bertoni, A., D. Bruschi, D. Joseph, M. Sitharam, and P. Young, "Generalized Boolean hierarchies and Boolean hierarchies over RP," final version prior to publication available as Univ Wisc CS Tech Report; short abstract in Proc. 7th Symp Foundations Computing Theory, (FCT- 1989), Springer-Verlag, LNCS 380, 35-46.
	2	Jin-Yi Cai , Thomas Gundermann , Juris Hartmanis , Lane A. Hemachandra , Vivian Sewelson , Klaus Wagner , Gerd Wechsung, The Boolean hierarchy I: structural properties, SIAM Journal on Computing, v.17 n.6, p.1232-1252, Dec. 1988 [doi>10.1137/0217078]
	3	J.-Y. Cai , T. Gundermann , G. Wechsung , J. Hartmanis , Lane A. Hemachandra , V. Sewelson , K. Wagner, The Boolean hierarchy II: applications, SIAM Journal on Computing, v.18 n.1, p.95-111, Feb. 1989 [doi>10.1137/0218007]
	4	[HL-91] S. Homer and L. Longpré, "On reductions of NP sets to sparse sets," Structure in Complexity Conference, 6 (1991), 79-88.
	5	Mitsunori Ogiwara , Osamu Watanabe, On polynomial-time bounded truth-table reducibility of NP sets to sparse sets, SIAM Journal on Computing, v.20 n.3, p.471-483, June 1991 [doi>10.1137/0220030]
	6	[Uk-83] E. Ukkonen, "Two results on polynomial time truth-table reductions to sparse sets," SIAM J Comput, 12 (1983), 580-587.
	7	[Wa-87] O. Watanabe, "Polynomial time reducibility to a set of small density," Structure in Complexity Conference, (1987), 138-146.
	8	Osamu Watanabe, On <=^P_{1-tt}-Sparseness and Nondeterministic Complexity Classes (Extended Abstract), Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.697-709, July 11-15, 1988
	9	[Ya-83] C. Yap, "Some consequences of non-uniform conditions on uniform classes," Theor Comput Sci 26 (1983), 287-300.
	10	[Ye-83] Y. Yesha, "On certain polynomial time truth-table reductions to sparse sets," SIAM J Comput, 12 (1983), 411-425.
	11	[AHHKLMOSST-92] V. Arvind, et al., "Reductions to sets of low information content," Technical Report, University of Rochester, C.S. Dept., 417 (April, 1992), 1-54.
	12	[AKM-92] V. Arvind, J. Köbler, and M. Mundhenk, "Bounded truth-table and conjunctive reductions to sparse and tally sets," Technical Report, Universität Ulm Fakultät für Informatik, 92-01 (April, 1992), 1-22.
	13	[Bi-92] Bin Fu, "With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets," Preprint, Beijing Computer Institute, (1992), 1-11.
	14	[BLS-92] H. Buhrman, Luc Longpré, and Edith Spaan, "Sparse reduces conjunctively to tally," Technical Report, Northeastern University, NU-CCS-92-8 (1992), 1-11.
	15	[RR-92] D. Ranjan and P. Rohatgi, "Randomized reductions to sparse sets," Proceedings 7th Structure in Complexity Theory Conference 7 (1992), to appear.
	16	Paul Young, How reductions to sparse sets collapse the polynomial-time hierarchy: a primer; part I: polynomial-time Turing reductions, ACM SIGACT News, v.23 n.3, p.107-117, Summer 1992 [doi>10.1145/141914.141921]