Complexity classes between θpk and Δpk

We give different characterizations of the classes P logi NP), which are located betweenΘ P 2 and Δ P 2 . First we show that these classes are equal AC i-1 (NP). Second we prove that they are also equivalent to certain binary search classes over NP. Third we show that they can be characterized as the classes defined by circuits of size O(log i n) with NP oracle gates. All the proofs given for these relationships remain valid under relativizations, so taking Σ P k instead of NP we can obtain similar characterizations for the classes P logi (Σ P k ), which are located between Θ P k+1 and Δ P k+1 .. These relationships can be used to prove Θ-lowness properties for some classes. In particular, we clarify the situation of the classes in L 2 P,Δ whose membership to L 2 P,Θ was not clear. With these results we solve open questions that arose in [Wa-90], [AW-90] and [LS-91]. Finally, we give an oracle relative to which classes P logi+1 (NP) are different.