Complexity classes between Θ k P and Δ k P

J. Castro; C. Seara

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

  • Volume: 30, Issue: 2, page 101-121
  • ISSN: 0988-3754

How to cite

top

Castro, J., and Seara, C.. "Complexity classes between $\Theta _k^P$ and $\Delta _k^P$." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.2 (1996): 101-121. <http://eudml.org/doc/92527>.

@article{Castro1996,
author = {Castro, J., Seara, C.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {complexity classes; binary search classes},
language = {eng},
number = {2},
pages = {101-121},
publisher = {EDP-Sciences},
title = {Complexity classes between $\Theta _k^P$ and $\Delta _k^P$},
url = {http://eudml.org/doc/92527},
volume = {30},
year = {1996},
}

TY - JOUR
AU - Castro, J.
AU - Seara, C.
TI - Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 1996
PB - EDP-Sciences
VL - 30
IS - 2
SP - 101
EP - 121
LA - eng
KW - complexity classes; binary search classes
UR - http://eudml.org/doc/92527
ER -

References

top
  1. [AH-92] E. ALLENDER and L. HEMACHANDRA, Lower bounds for the low hierarchy, Journal of the ACM, 1992, 39 (1), pp. 234-250. Zbl0799.68081MR1147302
  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. MR1097663
  3. [BB-86] J. L. BALCÁZAR and R. BOOK, Sets with small generalized Kolmogorov complexity, Acta Informatica, 1986, 23, pp. 679-688. Zbl0616.68046MR865501
  4. [BH-91] S. Buss and L. HAY, On truth-table reducibility to SAT, Information and Computation, 1991, 91, pp. 86-102. Zbl0800.68443MR1097264
  5. [BS-92] J. L. BALCÁZAR and U. SCHÖNING, Logarithmic advice classes, Theoretical Computer Science, 1992, 99, pp. 279-290. Zbl0761.68040MR1168464
  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. Zbl0688.68029MR1031365
  7. [Be-91] R. J. BEIGEL, Bounded queries to SAT and the Boolean hierarchy, Theoretical Computer Science, 1991, 84, pp. 199-223. Zbl0739.68035MR1118121
  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. Zbl0676.68011MR972671
  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. Zbl0611.68018MR854893
  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. Zbl0562.68033MR774926
  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. Zbl0642.03024MR928769
  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. Zbl0693.68027MR1030658
  13. [Kö-85] J. KÖBLER, Untersuchung verschiedener polynomieller Reduktionsklassen von NP, thesis, University of Stuttgart, 1985. 
  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. 
  15. [LT-91] A. LOZANO and J. TORÁN, Self-reducible sets of small density, Math. Systems Theory, 1991, 24, pp. 83-100. Zbl0722.68058MR1096693
  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. Zbl0493.68043MR680515
  17. [Og-94] M . OGIWARA, NCk(NP) = ACk-1 (NP), STACS 94, LNCS, 1994, 775, Springer-Verlag, pp. 313-324. Zbl0941.03539MR1288548
  18. [Sc-83] U. SCHÖNING, A low and a high hierarchy within NP, J. Comput. System Sci., 1983, 27, pp. 14-28, Zbl0515.68046MR730913
  19. [Sc-86a] U. SCHÖNING, Complete sets and closeness to complexity classes, Mathematical Systems Theory, 1986, 19, pp. 29-41. Zbl0617.68047MR840816
  20. [Sc-86b] U. SCHÖNING, Complexity and Structure, LNCS, 1986, 211, Springer-Verlag. Zbl0589.03022MR827009
  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. Zbl0581.68043MR821265
  22. [Wa-90] K. WAGNER, Bounded query classes, SIAM J. Comput., 1990, 19 (5), pp. 833-846. Zbl0711.68047MR1059657
  23. [Wi-87] C. B. WILSON, Relativized NC, Math. Systems Theory, 1987, 20, pp. 13-29. Zbl0627.68043MR901891
  24. [Wi-90] C. B. WILSON, Decomposing NC and AC, SIAM J. Comput., 1990, 19 (2), pp. 384-396. Zbl0692.68045MR1042734

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.