Abstract :
This paper defines natural hierarchies of function and relation classes □i,kc and Δi,kc, constructed from parallel complexity classes in a manner analogous to the polynomial-time hierarchy. It is easily shown that □i−1,kp ⊆ □c,kc ⊆ □i,kp and similarly for the Δ classes. The class □i,3c coincides with the single-valued functions in Buss et al.ʹs class View the MathML source (see [11]), and analogously for other growth rates. Furthermore, the class □i,kc comprises exactly the functions Σi,kb-definable in Ski−1, and if Tki−1 is ∀∃Σi,kb-conservative over Ski−1, then □i,kp is completely parallelizable. All functions in □i,kc are Σi,kb-definable in Rki; this suffices to show that if the known ∀∃Σi,kb conservativity between R3i and S3i−1 extends to R2i and S2i−1, then NC = NC1 relative to an oracle in PH. We prove a KPT-style witnessing theorem for Ski using constantly many rounds of □i,kc interactive computation, and thus show that if Ski ≡ Rki+1 then the bounded arithmetic hierarchy collapses, provably in Ski.
