Bounded arithmetic for NC, ALogTIME, L and NL (Q1192345)

The authors define theories of bounded arithmetic whose definable functions or relations are exactly those in certain complexity classes. They define a fragment TNC of bounded first-order arithmetic and prove that functions in the parallel complexity class NC are exactly those functions which are \(\Sigma^ b_ 1\)-definable in TNC. The class NC consists of all functions computable in polylogarithmic time with a polynomial number of processors on a parallel random-access machine. Then the authors define fragments of bounded second-order arithmetic such that suitably definable relations are, respectively, in the complexity classes ALogTIME, NL and L.