The low and high hierarchies: Refinement, extension, and structure

摘要

The low and high hierarchies within NP were introduced by Schoning (Sch83) to analyze the internal structure of NP. The high hierarchy starts at the NP-complete sets and grows "downward" towards P while the low hierarchy starts at P and grows "upward" towards the NP-complete sets. The low hierarchy, in particular, is a classification mechanism for the intermediate problems in NP. For example, it is known that Graph Isomorphism is in level two of the low hierarchy. The concept of low and high has been extended to sets outside NP (BBS86).;Based on $Delta$-classes of the polynomial-time hierarchy, refinements of the low and high hierarchies and of the extended low and extended high hierarchies were introduced in (Sch86, AH92). In this dissertation, we study a further refinement of the low and high hierarchies and the extended low hierarchy based on the $Theta$-classes of the polynomial-time hierarchy. We relocate most of the previously known sets that are in the $Delta$-levels of the low or extended low hierarchies to the refined $Theta$-levels.;One important question concerning the structure of the low and high hierarchies in NP and the extended low hierarchy is whether these hierarchies have an infinite number of distinct levels. In our second set of new results, we use circuit lower bound techniques from Yao, Hastad, and Ko and show that the extended low hierarchy is indeed an infinite hierarchy. This is the first such infinite hierarchy result concerning the structure of the low and high hierarchies and the extended low hierarchy.;Another important question concerning the structure of the low and high hierarchies is whether there is gap between the low and high hierarchies. If such a gap exists, what kind of NP sets fall into this gap? In our last set of new results, we investigate the class UP and its relationship to the low and high hierarchies. We show that relative to an oracle set UP contains a set that is not in any level of the low hierarchy and that UP and the high hierarchy are disjoint. A new type of random restriction and a new switching lemma are introduced to prove our new results.