Complexity classes between $\Theta _k^P$ and $\Delta _k^P$

Castro, J.; Seara, C.

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) no. 2, pp. 101-121.

MR Zbl

@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},
     pages = {101--121},
     publisher = {EDP-Sciences},
     volume = {30},
     number = {2},
     year = {1996},
     mrnumber = {1420686},
     zbl = {0860.68048},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1996__30_2_101_0/}
}

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
SP  - 101
EP  - 121
VL  - 30
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1996__30_2_101_0/
LA  - en
ID  - ITA_1996__30_2_101_0
ER  -

%0 Journal Article
%A Castro, J.
%A Seara, C.
%T Complexity classes between $\Theta _k^P$ and $\Delta _k^P$
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1996
%P 101-121
%V 30
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1996__30_2_101_0/
%G en
%F 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) no. 2, pp. 101-121. http://archive.numdam.org/item/ITA_1996__30_2_101_0/

Bibliographie
Cité par

[AH-92] E. Allender and L. Hemachandra, Lower bounds for the low hierarchy, Journal of the ACM, 1992, 39 (1), pp. 234-250. | MR | Zbl

[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

[BB-86] J. L. Balcázar and R. Book, Sets with small generalized Kolmogorov complexity, Acta Informatica, 1986, 23, pp. 679-688. | MR | Zbl

[BH-91] S. Buss and L. Hay, On truth-table reducibility to SAT, Information and Computation, 1991, 91, pp. 86-102. | MR | Zbl

[BS-92] J. L. Balcázar and U. Schöning, Logarithmic advice classes, Theoretical Computer Science, 1992, 99, pp. 279-290. | MR | Zbl

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

[Be-91] R. J. Beigel, Bounded queries to SAT and the Boolean hierarchy, Theoretical Computer Science, 1991, 84, pp. 199-223. | MR | Zbl

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

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

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

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

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

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

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

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

[Sc-83] U. Schöning, A low and a high hierarchy within NP, J. Comput. System Sci., 1983, 27, pp. 14-28, | MR | Zbl

[Sc-86a] U. Schöning, Complete sets and closeness to complexity classes, Mathematical Systems Theory, 1986, 19, pp. 29-41. | MR | Zbl

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

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

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

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

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