On counting problems and the polynomial-time hierarchy

AbstractWe consider the relation between the relativized polynomial time hierarchy and relativizations of Gill's class PP of sets recognizable in polynomial time by probabilistic Turing machines and of Valiant's class D≠P of sets polynomial time Turing reducible to functions that give the number of accepting computations of nondeterministic polynomial-time bounded Turing machines. The main result is that there exists an oracle set A such that PPA −(Π2P,A ∪ σ2P,A) ≠ ∅, with the corollary that also D ≠PA − (Π2P,A ∪ σ2P,A ≠ ∅. The proof is an application of Baker and Selman's technique for showing that σ2P,A ⊆ σ3P,A for some oracle set A