On boolean lowness and boolean highness

The concepts of lowness and highness originate from recursion theory and we re introduced into the complexity theory by Schoning (Lecture Notes in Comp uter Science, Vol. 211, Springer, Berlin, 1985). Informally, a set is low ( high resp.) for a relativizable class K of languages if it does not add (ad ds maximal resp.) power to K when used as an oracle. In this paper, we intr oduce the notions of boolean lowness and boolean highness. Informally, a se t is boolean low (boolean high resp.) for a class X of languages if it does not add (adds maximal resp.) power to K when combined with K by boolean op erations. We prove properties of boolean lowness and boolean highness which show a lot of similarities with the notions of lowness and highness. Using Kadin's technique of hard strings (see Kadin, SIAM J. Comput 17(6) (1988) 1263-1282; Wagner, Number-of-query hierachies, TR 158, University of Augsbu rg, 1987; Chang and Kadin SIAM J. Comput. 25(2) (1996) 340; Beigel ct al. M ath. Systems Theory 26 (1993) 293-310) we show that the sets which are bool ean low for the classes of the boolean hierarchy are low for the boolean cl osure of Sigma (p)(2). Furthermore, we prove a result on boolean lowness wh ich has as a corollary the best known result (sec Beigel, (1993); in fact e ven a bit better) on the connection of the collapses of the boolean hierarc hy and the polynomial-lime hierarchy if BH = NP(L) then PH = Sigma (p)(2)(k - 1) circle plus NP(k). (C) 2001 Published by Elsevier Science B.V.