Complexity classes between Θ k P and Δ k P
Castro, J. ; Seara, C.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996), p. 101-121 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1996-01-01
@article{ITA_1996__30_2_101_0,
     author = {Castro, J. and Seara, C.},
     title = {Complexity classes between $\Theta \_k^P$ and $\Delta \_k^P$},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {30},
     year = {1996},
     pages = {101-121},
     mrnumber = {1420686},
     zbl = {0860.68048},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1996__30_2_101_0}
}

Castro, J.; Seara, C. Complexity classes between $\Theta _k^P$ and $\Delta _k^P$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) pp. 101-121. http://gdmltest.u-ga.fr/item/ITA_1996__30_2_101_0/

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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

[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. | Numdam | MR 928769 | Zbl 0642.03024

[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

[Kö-85] J. Köbler, Untersuchung verschiedener polynomieller Reduktionsklassen von NP, thesis, University of Stuttgart, 1985.

[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.

[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

[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

[Og-94] M . Ogiwara, NCk(NP) = ACk-1 (NP), STACS 94, LNCS, 1994, 775, Springer-Verlag, pp. 313-324. | MR 1288548 | Zbl 0941.03539

[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

[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

[Sc-86b] U. Schöning, Complexity and Structure, LNCS, 1986, 211, Springer-Verlag. | MR 827009 | Zbl 0589.03022

[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

[Wa-90] K. Wagner, Bounded query classes, SIAM J. Comput., 1990, 19 (5), pp. 833-846. | MR 1059657 | Zbl 0711.68047

[Wi-87] C. B. Wilson, Relativized NC, Math. Systems Theory, 1987, 20, pp. 13-29. | MR 901891 | Zbl 0627.68043

[Wi-90] C. B. Wilson, Decomposing NC and AC, SIAM J. Comput., 1990, 19 (2), pp. 384-396. | MR 1042734 | Zbl 0692.68045