On boolean lowness and boolean highness

Theoretical Computer Science - Tập 261 - Trang 305-321 - 2001
Steffen Reith1, Klaus W. Wagner1
1Lehrstuhl für Theoretische Informatik, Universität Würzburg, Am Hubland 97074 Würzburg, Germany

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