The Boolean hierarchy [1] captures the power of finite hardware combining NP languages, and the levels of the Boolean hierarchy attempt to provide a measure for the amount of well-structured use of hardware of any given set in the Boolean closure of NP. It is well known that the Boolean hierarchy’s levels have many equivalent normal forms, for example, as finite nested differences of NP sets. For instance, the third level of the hierarchy is { L | ( ∃ L 1 , L 2 , L 3 ∈ NP [ L = L 1 - ( L 2 - L 3 ) ]}.
Two other notions of structured, bounded access to NP are k -truth-table reductions and k -Turing reductions. It is natural to study the interrelations between the Boolean hierarchy and the truth-table and Turing hierarchies, and this has been done in a large number of papers, which the reader should probably look at together with this paper [2,3]. One issue left open by the earlier papers was the exact location within the Boolean hierarchy’s levels of the Turing hierarchy’s levels. This paper resolves that question to within one level. The author goes on to provide a number of nice tools for understanding bounded access, provides second proofs for many known results, and studies generalizations of various bounded hierarchies. The final sections study the connection between bounded query classes (both function and language classes) and terseness theory [4].
