Strong separations of the polynomial hierarchy with oracles: Constructive separations by immune and simple sets (Q1199689)

Two classes of sets \(C_ 1\) and \(C_ 2\) are strongly separated if there is an infinite set \(A\) in \(C_ 2\) which is immune for \(C_ 1\), that means no infinite subset of \(A\) is in \(C_ 1\). Strong separations are shown, in a relativized setting, for virtually all pairs of classes of the polynomial-time hierarchy. This paper combines several previously known nontrivial techniques (in a non-trivial way), essentially such steming from lower bound proofs for bounded-depth circuits (involving probabilistic arguments).