Sparse Oracles And Uniform Complexity Classes

Abstract

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.