@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://www.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://www.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://www.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://www.numdam.org/item/ITA_1996__30_2_101_0/
[AH-92] Lower bounds for the low hierarchy, Journal of the ACM, 1992, 39 (1), pp. 234-250. | MR | Zbl
and ,[AW-90] Width-bounded reducibility and binary search over complexity classes, Proc. 5th IEEE Conf.on Structure in Complexity Theory, 1990, pp. 122-129. | MR
and ,[BB-86] Sets with small generalized Kolmogorov complexity, Acta Informatica, 1986, 23, pp. 679-688. | MR | Zbl
and ,[BH-91] On truth-table reducibility to SAT, Information and Computation, 1991, 91, pp. 86-102. | MR | Zbl
and ,[BS-92] Logarithmic advice classes, Theoretical Computer Science, 1992, 99, pp. 279-290. | MR | Zbl
and ,[BT-89] A note on sparse sets and the polynomialtime hierarchy, Information Processing Letters, 1989, 33 (3), pp. 141-143. | MR | Zbl
and ,[Be-91] Bounded queries to SAT and the Boolean hierarchy, Theoretical Computer Science, 1991, 84, pp. 199-223. | MR | Zbl
,[CGHHSWW-88] The Boolean hierarchy I: Structural Properties, SIAM J. Comp., 1988, 17 (6), pp. 1232-1252. | MR | Zbl
, , , , , and ,[CH-86] The Boolean hierarchy: hardware over NP, Proc. Ist Conference on Structure in Complexity Theory, LNCS, 1986, 223, Springer-Verlag, pp. 105-124. | MR | Zbl
and ,[KS-85] On circuit-size and the low hierarchy in NP, SIAM J. Comput., 1985, 14 (1), pp. 41-51. | MR | Zbl
and ,[KSW-87] The difference and the truth-table hierarchies for NP, R.A.I.R.O., 1987, 21, pp. 419-435. | Numdam | MR | Zbl
, and ,[Ka-89] PNP [log n] and sparse Turing-complete sets for NP, J. Comput System Sci., 1989, 39 (3), pp. 282-298. | MR | Zbl
,[Kö-85] Untersuchung verschiedener polynomieller Reduktionsklassen von NP, thesis, University of Stuttgart, 1985.
,[LS-91] A refinement of the low and high hierarchies, Technical report OSU-CISRC-2/91-TR6, The Ohio State University, 1991.
and ,[LT-91] Self-reducible sets of small density, Math. Systems Theory, 1991, 24, pp. 83-100. | MR | Zbl
and ,[Ma-82] 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] NCk(NP) = ACk-1 (NP), STACS 94, LNCS, 1994, 775, Springer-Verlag, pp. 313-324. | MR | Zbl
,[Sc-83] A low and a high hierarchy within NP, J. Comput. System Sci., 1983, 27, pp. 14-28, | MR | Zbl
,[Sc-86a] Complete sets and closeness to complexity classes, Mathematical Systems Theory, 1986, 19, pp. 29-41. | MR | Zbl
,[Sc-86b] Complexity and Structure, LNCS, 1986, 211, Springer-Verlag. | MR | Zbl
,[WW-85] 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
and ,[Wa-90] Bounded query classes, SIAM J. Comput., 1990, 19 (5), pp. 833-846. | MR | Zbl
,[Wi-87] Relativized NC, Math. Systems Theory, 1987, 20, pp. 13-29. | MR | Zbl
,[Wi-90] Decomposing NC and AC, SIAM J. Comput., 1990, 19 (2), pp. 384-396. | MR | Zbl
,