Abstract:
Boolean hierarchies are central structures in complexity theory. The boolean hierarchy over a complexity class C is a concept to study sets that can be defined in terms of set theoretic operations on sets from C. In particular, the boolean hierarchy (over NP) has received much interest in the past, but also boolean hierarchies over other classes such as UP or R have been studied. In this thesis we concentrate on boolean hierarchies over the "Sigma"-levels of the polynomial hierarchy. We present new results on induced collapses, such as the induced collapse of the polynomial hierarchy that follows from a collapse of the boolean hierarchy and downward collapses within boolean hierarchies, as well as results on query order.
In Chapter 3 we study the connection between a collapse of the boolean hierarchy (over NP) and a collapse of the polynomial hierarchy. It is known that a collapse of the boolean hierarchy implies a collapse of the polynomial hierarchy (Kadin 1988). The depth of the induced collapse of the polynomial hierarchy has been improved four times (Wagner 1987, 1989, Chang and Kadin 1996, Beigel, Chang, and Ogihara 1993). We review the work, results and proof techniques of the above mentioned five papers and thus provide a compact historic outline of this interesting line of research together with a detailed analysis of the evolution of the easy-hard technique which, introduced by Kadin, has led to increasingly stronger results in the before mentioned papers. We improve the best known result by proving a deeper induced collapse of the polynomial hierarchy.
Chapter 4 of the thesis is devoted to the study of downward collapse with respect to boolean hierarchies. Proving upward and downward collapse results is a elegant method to tie together the relative powers of different computing paradigms. In contrast to upward collapse results (most hierarchies such as the polynomial hierarchy and the boolean hierarchy display upward collapse) downward collapse results are rather rare. In 1996 Hemaspaandra, Hemaspaandra, and Hempel obtained the first downward collapse result linking classes of bounded-query hierarchies and classes of the polynomial hierarchy and initiated the search for similar downward collapse results (Buhrman and Fortnow 1998, Hemaspaandra, Hemaspaandra, and Hempel 1997, 1999). Though all of the followup results are based on the proof technique used by Hemaspaandra et. al 1996, which itself is a modification of Kadin's easy-hard technique, each new downward collapse result added some crucial and elegant enrichment to the proof technique itself. In analogy to the structure of Chapter 3 (and adopting the presentation of the material) we review this interesting development. Together with the corresponding part of Chapter 3, the thesis thus contains a complete technical overview over the development of the easy-hard technique ranging from Kadin's original work to the recent downward collapse results. We prove a new downward collapse result that strengthens a result from Hemaspaandra et. al. 1997 and removes an asymmetry in that result's hypothesis. Our proof exploits the easy-hard technique not only in its recently modified form as described in this chapter but also in its original form that has been studied in detail in Chapter 3.
Chapter 5 studies the computational power of the order of oracle queries. We try to determine whether the every-day life intuition that the order in which information sources are accessed matters carries over into complexity theory. We show that (in almost all cases) the order of queries to levels of the boolean hierarchy is important for the computational power of the resulting class unless the polynomial hierarchy collapses. We achieve this by characterizing query order classes in terms of reducibility cones of NP. Relatedly, it has been shown that query order in the polynomial hierarchy never matters (Hemaspaandra, Hemaspaandra, and Hempel 1997). This does not only hold in the case of two sequential queries (or two rounds of at most one query) to oracles from levels of the polynomial hierarchy but also in its generalization to more than one query in each round (Beigel and Chang 1997). These more general results miss the case that the query rounds consist of queries to oracles from the same level of the polynomial hierarchy. We solve this missing case and show that also in this case the order of query rounds can be exchanged without losing computational power. The result follows from a characterization of this special type of query order classes in terms of reducibility cones of the underlying level of the polynomial hierarchy.
Table of contents:
