Restricted relativizations of probabilistic polynomial time (Q1186606)

The complexity class PP ( probabilistic polynomial time) is analyzed and its relation to the classes PH (the polynomial-time hierarchy) and PSPACE (polynomial space) are considered. A quantitive restriction on the access mechanism to a given oracle is introduced. Positive relativization results with respect to sparse oracles, and with respect to the question PP = PSPACE and PP = PH are proved. Later results by the same author show that PP is indeed a very powerful class, namely, PH is included in P(PP).