On boolean lowness and boolean highness (Q5941441): Difference between revisions

The concepts of lowness and highness originate from recursion theory and were introduced into the complexity theory by \textit{U. Schöning} [Lect. Notes Comput. Sci. 211 (1985; Zbl 0589.03022)]. Informally, a set is low (high resp.) for a relativizable class \(K\) of languages if it does not add (adds maximal resp.) power to \(K\) when used as an oracle. In this paper, we introduce the notions of boolean lowness and boolean highness. Informally, a set is boolean low (boolean high resp.) for a class \(K\) of languages if it does not add (adds maximal resp.) power to \(K\) when combined with \(K\) by boolean operations. 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 \textit{J. Kadin}, SIAM J. Comput 17, No. 6, 1263-1282 (1988; Zbl 0664.03031); \textit{K. W. Wagner}, Number-of-query hierachies, TR 158, University of Augsburg (1987); \textit{R. Chang} and \textit{J. Kadin}, SIAM J. Comput. 25, No. 2, 340-354 (1996; Zbl 0844.68048); (*) \textit{R. Beigel, R. Chang} and \textit{M. Ogiwara}, Math. Syst. Theory 26, No. 3, 293-310 (1993; Zbl 0776.68043)] we show that the sets which are boolean low for the classes of the boolean hierarchy are low for the boolean closure of \(\Sigma_{2}^{p}\). Furthermore, we prove a result on boolean lowness which has as a corollary the best known result (*); in fact even a bit better) on the connection of the collapses of the boolean hierarchy and the polynomial-time hierarchy if \(BH = NP(k)\) then \(PH = \Sigma_{2}^{k-1}\oplus NP(k)\).