COMPLEXITY CLASSES BETWEEN Θ_k~P AND Δ_k~P

摘要

We give different characterizations of the classes P_(log~i) (NP), which are located between Θ_2~P and Δ_2~P. First we show that these classes are equal to the classes 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 Σ_k~P instead of NP we can obtain similar characterizations for the classes P_(log~i) (Σ_k~P), which are located between Θ_(k+1)~P and Δ_(k+1)~P. 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_(log~i) (NP) and P_(log~(i+1)) (NP) are different.