Separating the low and high hierarchies by oracles (Q2638773): Difference between revisions
From MaRDI portal
Revision as of 13:45, 21 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Separating the low and high hierarchies by oracles |
scientific article |
Statements
Separating the low and high hierarchies by oracles (English)
0 references
1991
0 references
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.
0 references
oracles
0 references
low hierarchy
0 references
high hierarchy
0 references