On parallel hierarchies and \(R_k^i\) (Q1377627)

This paper defines natural hierarchies of function and relation classes \(\square^c_{i,k}\) and \(\Delta^c_{i,k}\), constructed from parallel complexity classes in a manner analogous to the polynomial-time hierarchy. The class \(\square^c_{i,k}\) comprises exactly the functions \(\Sigma^b_{i,k}\)-definable in \(S_k^{i-1}\); and if \(T^{i-k}_k\) is \(\forall \exists \Sigma^b_{i,k}\)-conservative over \(S_k^{i-1}\), then \(\square^p_{i,k}\) is completely parallelizable. If the known \(\forall \exists \Sigma^b_{i,k}\) conservativity between \(R^i_3\) and \(S_3^{i-1}\) extends to \(R^i_2\) and \(S_2^{i-1}\), then \(\text{NC}= \text{NC}^1\) relative to an oracle in PH. The author proves a KPT-style witnessing theorem for \(S^i_k\) using constantly many rounds of \(\square^c_{i,k}\) interactive commutation, and shows that if \(S^i_k \equiv R_k^{i+1}\) then the bounded arithmetic hierarchy collapses, provably in \(S^i_k\).