Separating the low and high hierarchies by oracles (Q2638773): Difference between revisions

The low hierarchy is an infinite sequence of classes in NP that starts with P and generalizes the notion of ``easiness'' in NP. The high hierarchy similarly generalizes the notion of ``hardness'', i.e. NP- completeness in NP. The author shows that in a relativized setting (i.e. permitting oracles) an oracle A exists which forces the low and high hierarchies relative to A to be infinite. Furthermore, for each k an oracle set \(A_ k\) exists which forces the low and high hierarchies to have exactly k levels.