Abstract
The low hierarchy in NP [Sc-83] and the extended low hierarchy [BBS-86] have been useful in characterizing the complexity of certain interesting classes of sets. However, until now, there has been no way of judging whether or not a given lowness result is the best possible.
We prove absolute lower bounds on the location of classes is the extended low hierarchy, and relativized lower bounds on the location of classes in the low hierarchy in NP. In some cases, we are able to show that the classes are lower in the hierarchies than was known previously. In almost all cases, we are able to prove that our results are essentially optimal.
We also examine the interrelationships among the levels of the low hierarchies and the classes of sets reducible to or equivalent to sparse and tally sets under different notions of reducibility. We feel that these results clarify the structure underlying the low hierarchies.