EDP Sciences logo
Subscriber Authentication Point
Search
Menu
All issues Volume 30 / No 2 (1996) RAIRO-Theor. Inf. Appl., 30 2 (1996) 101-121 References
Free Access
Issue
RAIRO-Theor. Inf. Appl.
Volume 30, Number 2, 1996
Page(s) 101 - 121
DOI https://doi.org/10.1051/ita/1996300201011
Published online 01 February 2017
  1. [AH-92] E. ALLENDER and L. HEMACHANDRA, Lower bounds for the low hierarchy, Journal of the ACM, 1992, 39 (1), pp. 234-250. [MR: 1147302] [Zbl: 0799.68081] [Google Scholar]
  2. [AW-90] E. ALLENDER and C. B. WILSON, Width-bounded reducibility and binary search over complexity classes, Proc. 5th IEEE Conf.on Structure in Complexity Theory, 1990, pp. 122-129. [MR: 1097663] [Google Scholar]
  3. [BB-86] J. L. BALCÁZAR and R. BOOK, Sets with small generalized Kolmogorov complexity, Acta Informatica, 1986, 23, pp. 679-688. [MR: 865501] [Zbl: 0616.68046] [Google Scholar]
  4. [BH-91] S. Buss and L. HAY, On truth-table reducibility to SAT, Information and Computation, 1991, 91, pp. 86-102. [MR: 1097264] [Zbl: 0800.68443] [Google Scholar]
  5. [BS-92] J. L. BALCÁZAR and U. SCHÖNING, Logarithmic advice classes, Theoretical Computer Science, 1992, 99, pp. 279-290. [MR: 1168464] [Zbl: 0761.68040] [Google Scholar]
  6. [BT-89] R. BOOK and S. TANG, A note on sparse sets and the polynomialtime hierarchy, Information Processing Letters, 1989, 33 (3), pp. 141-143. [MR: 1031365] [Zbl: 0688.68029] [Google Scholar]
  7. [Be-91] R. J. BEIGEL, Bounded queries to SAT and the Boolean hierarchy, Theoretical Computer Science, 1991, 84, pp. 199-223. [MR: 1118121] [Zbl: 0739.68035] [Google Scholar]
  8. [CGHHSWW-88] J. CAI, T. GUNDERMANN, J. HARTMANIS, L. HEMACHANDRA, V. SEWELSON, K. WAGNER and G. WECHSUNG, The Boolean hierarchy I: Structural Properties, SIAM J. Comp., 1988, 17 (6), pp. 1232-1252. [MR: 972671] [Zbl: 0676.68011] [Google Scholar]
  9. [CH-86] J. CAI and L. HEMACHANDRA, The Boolean hierarchy: hardware over NP, Proc. Ist Conference on Structure in Complexity Theory, LNCS, 1986, 223, Springer-Verlag, pp. 105-124. [MR: 854893] [Zbl: 0611.68018] [Google Scholar]
  10. [KS-85] K. Ko and U. SCHÖNING, On circuit-size and the low hierarchy in NP, SIAM J. Comput., 1985, 14 (1), pp. 41-51. [MR: 774926] [Zbl: 0562.68033] [Google Scholar]
  11. [KSW-87] J. KÖBLER, U. SCHÖNING and K. WAGNER, The difference and the truth-table hierarchies for NP, R.A.I.R.O., 1987, 21, pp. 419-435. [EuDML: 92293] [MR: 928769] [Zbl: 0642.03024] [Google Scholar]
  12. [Ka-89] J. KADIN, PNP [log n] and sparse Turing-complete sets for NP, J. Comput System Sci., 1989, 39 (3), pp. 282-298. [MR: 1030658] [Zbl: 0693.68027] [Google Scholar]
  13. [Kö-85] J. KÖBLER, Untersuchung verschiedener polynomieller Reduktionsklassen von NP, thesis, University of Stuttgart, 1985. [Google Scholar]
  14. [LS-91] T. LONG and M-J. SHEU, A refinement of the low and high hierarchies, Technical report OSU-CISRC-2/91-TR6, The Ohio State University, 1991. [Google Scholar]
  15. [LT-91] A. LOZANO and J. TORÁN, Self-reducible sets of small density, Math. Systems Theory, 1991, 24, pp. 83-100. [MR: 1096693] [Zbl: 0722.68058] [Google Scholar]
  16. [Ma-82] S. MAHANEY, Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis, J. Comput. System Sci., 1982, 25, pp. 130-143. [MR: 680515] [Zbl: 0493.68043] [Google Scholar]
  17. [Og-94] M . OGIWARA, NCk(NP) = ACk-1 (NP), STACS 94, LNCS, 1994, 775, Springer-Verlag, pp. 313-324. [MR: 1288548] [Zbl: 0941.03539] [Google Scholar]
  18. [Sc-83] U. SCHÖNING, A low and a high hierarchy within NP, J. Comput. System Sci., 1983, 27, pp. 14-28, [MR: 730913] [Zbl: 0515.68046] [Google Scholar]
  19. [Sc-86a] U. SCHÖNING, Complete sets and closeness to complexity classes, Mathematical Systems Theory, 1986, 19, pp. 29-41. [MR: 840816] [Zbl: 0617.68047] [Google Scholar]
  20. [Sc-86b] U. SCHÖNING, Complexity and Structure, LNCS, 1986, 211, Springer-Verlag. [MR: 827009] [Zbl: 0589.03022] [Google Scholar]
  21. [WW-85] G. WECHSUNG and K. WAGNER, On the Boolean closure of NP, manuscript 1985 (extended abstract as: G. Wechsung, On the Boolean closure of NP, Proc. Conf. Fundam. Comp. Theory, Cottbus 1985, LNCS, 1985, 199, pp. 485-493. [MR: 821265] [Zbl: 0581.68043] [Google Scholar]
  22. [Wa-90] K. WAGNER, Bounded query classes, SIAM J. Comput., 1990, 19 (5), pp. 833-846. [MR: 1059657] [Zbl: 0711.68047] [Google Scholar]
  23. [Wi-87] C. B. WILSON, Relativized NC, Math. Systems Theory, 1987, 20, pp. 13-29. [MR: 901891] [Zbl: 0627.68043] [Google Scholar]
  24. [Wi-90] C. B. WILSON, Decomposing NC and AC, SIAM J. Comput., 1990, 19 (2), pp. 384-396. [MR: 1042734] [Zbl: 0692.68045] [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.