Title: UP and the low and high hierarchies: A relativized separation
Abstract: The low and high hierarchies within NP were introduced by Schöning in order to classify sets in NP. It is not known whether the low and high hierarchies include all sets in NP. In this paper, we provide evidence that the class UP may fall in the gap between the low and high hierarchies. Using the circuit lower bound techniques of Håstad and Ko, we construct an oracle set relative to which UP is not in any level of the low and high hierarchies. Since it is known that UPA is low for PPA for all sets A, our result also shows that the interaction between UP and PP is crucial for the lowness of UP for PP; changing the base class to any level of the polynomial-time hierarchy destroys the lowness of UP.
Publication Year: 1992
Publication Date: 1992-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 2
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot