ECCC-Report TR05-017https://eccc.weizmann.ac.il/report/2005/017Comments and Revisions published for TR05-017en-usFri, 04 Feb 2005 16:40:34 +0200
Paper TR05-017
| Two-Sorted Theories for L, SL, NL and P |
Phong Nguyen
https://eccc.weizmann.ac.il/report/2005/017We 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.
Fri, 04 Feb 2005 16:40:34 +0200https://eccc.weizmann.ac.il/report/2005/017