Authors: Richard Beigel, Richard Chang, and Mitsunori Ogiwara

Abstract: Chang and Kadin have shown that if the difference hierarchy over NP collapses to level k, then the polynomial hierarchy (PH) is equal the kth level of the difference hierarchy over Σ₂^p. We simplify their proof and obtain a slightly stronger conclusion: If the difference hierarchy over NP collapses to level k, then PH collapses to (P_{(k - 1)-tt}^NP)^NP, the class of sets recognized in polynomial time with k - 1 nonadaptive queries to a set in NP^NP and an unlimited number of queries to a set in NP. We also extend the result to classes other than NP: For any class C that has ≤_m^p-complete sets and is closed under ≤^p_conj- and ≤_m^NP-reductions (alternatively, closed under ≤^p_disj- and ≤_m^co-NPreductions), if the difference hierarchy over C collapses to level k, then PH^C = (P_{(k - 1)-tt}^NP)^C. Then we show that the exact counting class C₌P is closed under ≤^p_disj- and ≤_m^co-NP-reductions. Consequently, if the difference hierarchy over C₌P collapses to level k then PH^PP (= PH^C₌P) is equal to (P_{(k - 1)-tt}^NP)^PP. In contrast, the difference hierarchy over the closely related class PP is known to collapse.

Finally we consider two ways of relativizing the bounded query class P_k-tt^NP: the restricted relativization P_k-tt^NPC, and the full relativization (P_k-tt^NP)^C. If C is NP-hard, then we show that the two relativizations are different unless PH^C collapses.

Download Full Paper