On boolean lowness and boolean highness
Tài liệu tham khảo
Beigel, 1993, A relationship between difference hierarchies and relativized polynomial hierarchies, Math. Systems Theory, 26, 293, 10.1007/BF01371729
Cai, 1988, The boolean hierarchy I, SIAM J. Comput., 17, 1232, 10.1137/0217078
Cai, 1986, Vol. 223, 105
R. Chang, Bounded queries, approximation and the boolean hierarchy, Tech. Rep. CS 97-04, University of Maryland, Department of Computer Science and Electrical Engineering, 1997.
Chang, 1996, The boolean hierarchy and the polynomial hierarchy, SIAM J. Comput., 25, 340, 10.1137/S0097539790178069
Cooper, 1974, Minimal pairs and high recursively enumerable degree, J. Symbolic Logic, 39, 655, 10.2307/2272849
E. Hemaspaandra, L.A. Hemaspaandra, H. Hempel, What's up with downward collapse: using the easy-hard technique to link boolean and polynomial hierarchy collapses, UR-CS-TR-98-682, University of Rochester, Department of Computer Science, 1998.
Kadin, 1988, The polynomial time hierarchy collapses if the boolean hierarchy collapses, SIAM J. Comput., 17, 1263, 10.1137/0217080
Karp, 1980, 302
J. Köbler, Untersuchungen verschiedener polynomieller Reduktionsklassen von NP, Diploma Thesis, Universität Stuttgart, 1985.
Köbler, 1987, he difference and truth-table hierarchies for NP, Theoret. Inform. Appl., 21, 419, 10.1051/ita/1987210404191
Schöning, 1983, A low and a high hierarchy within NP, J. Comput. System Sci., 27, 14, 10.1016/0022-0000(83)90027-2
Schöning, 1985, Vol. 211
Soare, 1974, Automorphisms of the lattice of recursively enumerable sets, Bull. Amer. Math. Soc., 80, 53, 10.1090/S0002-9904-1974-13350-1
K.W. Wagner, Number-of-query hierachies, Tech. Rep. 158, University of Augsburg, 1987.
K.W. Wagner, A note on bounded queries and the difference hierarchy, Tech. Rep. 173, Institut für Informatik, Universität Würzburg, 1997.
Wechsung, 1985, Vol. 199, 485