Sparse Oracles and Uniform Complexity Classes

We show that several questions about the polynomial-time hierarchy can be answered by answering their counterparts for the polynomial-time hierarchy relativized to an arbitrary sparse oracle set. For each of these questions, the answer will be the same for the hierarchy relativized to S/sub 1/ as it will be for the hierarchy relativized to S/sub 2/ for any choice of S/sub 1/ and S/sub 2/ that are sparse sets, including the choice of S/sub 1/ being empty and S/sub 2/ being nonempty but sparse.

Authors

• José L. Balcázar
• Ronald V. Book
• Timothy J. Long
• Uwe Schöning
• Alan L. Selman

Keywords

• Polynomials
• Computer science
• Mathematics
• Cultural differences
• Proof Of Theorem