questions,“Does the polynomial-time hierarchy collapse?” and “Is the union of the hierarchy
equal to PSPACE?” are considered, along with others comparing the union of the hierarchy
with certain probabilistic classes. In each case it is shown that the answer is “yes” if and only
if for every sparse set S, the answer is “yes” when the classes are relativized to S if and only
if there exists a sparse set S such that the answer is “yes” when the classes are relativized to …