General Method to Construct Oracles Realizing Given Relationships BetweenComplexity Classes

摘要

We present a method to prove oracle results of the following type. Let K(sub1),..., K(sub 2n) and L(sub 1),..., L(sub 2m) be complexity classes. Our method provides a general framework for constructing an oracle A such that K(sup A, sub 2i-1) does not equal K(sup A, sub 2i) for i = 1,..., n and L(sup A, sub 2j-1) equals L(sup A, sub 2j) for j = 1,..., m. Using that method we prove several results of this kind. The hardest of them is the existence of an oracle A such that P(sup A) does not equal NP(sup A), P(sup A)equals BPP(sup A) and both Co-NP(sup A)-sets and NP(sup A)-sets are P(sup A)-separable. We exhibit also two theorems that cannot be proved by that method.