Abstract:
We introduce ``minimal'' two--sorted first--order theories VL, VSL, VNL and VP that characterize the classes L, SL, NL and P in the same way that Buss's $S^i_2$ hierarchy characterizes the polynomial time hierarchy. Our theories arise from natural combinatorial problems, namely the st-Connectivity Problem and the Circuit Value Problem. It turns out that VL is the same as Zambella's $\Sigma_0^B-Rec$, VP is the same as Cook's $TV^0$, and VNL and VSL are respectively the same as V-Krom and Kolokolova's V-SymKrom. Except for $VL = \Sigma_0^B-Rec$, establishing these equivalences is non-trivial.