Let H be a proof system for quantified propositional calculus (QPC). We define the Σqj-witnessing problem for H to be: given a prenex Σqj-formula A, an H-proof of A, and a truth assignment to the free variables in A, find a witness for the outermost existential quantifiers in A. We point out that the Σq1-witnessing problems for the systems G*1and G1 are complete for polynomial time and PLS (polynomial local search), respectively. We introduce and study the systems G*0 and G0, (...) in which cuts are restricted to quantifier-free formulas, and prove that the Σqj-witnessing problem for each is complete for NC1. Our proof involves proving a polynomial time version of Gentzen’s midsequent theorem for G*0 and proving that G0-proofs are TC0-recognizable. We also introduce QPC systems for TC0 and prove witnessing theorems for them. We introduce a finitely axiomatizable second-order system VNC1 of bounded arithmetic which we prove isomorphic to Arai’s first order theory AID + Σb0-CA for uniform NC1. We describe simple translations of VNC1 proofs of all bounded theorems to polynomial size families of G*0 proofs. From this and the above theorem we get alternative proofs of the NC1 witnessing theorems for VNC1 and AID. (shrink)

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 , 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. (shrink)