EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 30 / No 2 (1996) RAIRO-Theor. Inf. Appl., 30 2 (1996) 91-100 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 30, Number 2, 1996
Page(s) 91 - 100
DOI https://doi.org/10.1051/ita/1996300200911
Published online 01 February 2017
  1. 1. E. ALLENDER, L. A. HEMACHANDRA, M. OGIWARA, and O. WATANABE, Relating equivalence and reducibility to sparse sets, SIAM Journal on Computing, 1992, 2, pp. 521-539. [MR: 1163344] [Zbl: 0761.68039] [Google Scholar]
  2. 2. A. AMIR, R. BEIGEL and W. I. GASARCH, Some connections between bounded query classes and non-uniform complexity, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 232-243. [Zbl: 1058.68056] [MR: 1097673] [Google Scholar]
  3. 3. R. BEIGEL, Query-limited Reducibilities, PhD thesis, Stanford University, 1987. [MR: 2636225] [Google Scholar]
  4. 4. R. BEIGEL, Bounded queries to SAT and the boolean hierarchy, Theoretical Computer Science, 1991, 84 (2), pp. 199-223. [MR: 1118121] [Zbl: 0739.68035] [Google Scholar]
  5. 5. R. BEIGEL, R. CHANG, and M. OGIWARA, A relationship between difference hierarchies and relativized polynomial hierarchies, Mathematical Systems Theory, 1993, 26 (3), pp. 293-310. [MR: 1209999] [Zbl: 0776.68043] [Google Scholar]
  6. 6. R. CHANG, On the structure of bounded queries to arbitrary NP sets, SIAM Journal on Computing, 1992, 21 (4), pp. 743-754. [MR: 1171859] [Zbl: 0749.68034] [Google Scholar]
  7. 7. R. CHANG and J. KADIN, The boolean hierarchy and the polynomial hierarchy: a closer connection, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 169-178. To appear in SIAM Journal on Computing. [MR: 1097667] [Zbl: 0844.68048] [Google Scholar]
  8. 8. F. GREEN, On the power of deterministic reductions to C = P, Manuscript, April 1991. [Google Scholar]
  9. 9. T. GUNDERMAN, N. NASSER, and G. WECHSUNG, A survey of counting classes, Proceedings of the 5th Structure in Complexity Theory Conference, 1990, pp. 140-153. [MR: 1097665] [Google Scholar]
  10. 10. L. A. HEMACHANDRA, Counting in structural complexity theory, PhD thesis, Cornell University, June 1987. [Google Scholar]
  11. 11. J. KADIN, IS one NP question as powerful as two?, Technical Report TR 87-842, Cornell University, June 1987. [Google Scholar]
  12. 12. J. KADIN, Restricted Turing reducibilities and the structure of the Polynomial Time Hierarchy, PhD thesis, Cornell University, February 1988. [Zbl: 0664.03031] [Google Scholar]
  13. 13. J. KADIN, The polynomial time hierarchy collapses if the boolean hierarchy collapses, SIAM Journal on Computing, 1988, 17 (6), pp. 1263-1282. [MR: 972673] [Zbl: 0664.03031] [Google Scholar]
  14. 14. J. KADIN, Erratum to [13], SIAM Journal on Computing, 1991, 20 (2), p. 104. [MR: 1087757] [Google Scholar]
  15. 15. R. E. LADNER, N. A. LYNCH, and A. L. SELMAN, A comparison of polynomial time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. [MR: 395319] [Zbl: 0321.68039] [Google Scholar]
  16. 16. M. OGIWARA, On the computational power of exact counting, unpublished manuscript, April 1990. [Google Scholar]
  17. 17. M. OGIWARA, Generalized theorems on relationships among reducibility notions to certain complexity classes, Mathematical Systems Theory, 1984, 27, pp. 189-200. [MR: 1264385] [Zbl: 0813.68105] [Google Scholar]
  18. 18. M. OGIWARA and L. A. HEMACHANDRA, A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46 (3), pp. 295-325. [MR: 1228809] [Zbl: 0798.68060] [Google Scholar]
  19. 19. J. SIMON, On some central problems in computational complexity, PhD thesis, Cornell University, January 1975. [Google Scholar]
  20. 20. J. TORÁN, Structural properties of the Counting Hierarchy, PhD thesis, Universitat Politècnica de Catalunya, January 1990. [Zbl: 0733.68035] [Google Scholar]
  21. 21. K. W. WAGNER, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. [MR: 853581] [Zbl: 0621.68032] [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.