Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-017 | 28th January 2005 00:00

Two-Sorted Theories for L, SL, NL and P

RSS-Feed




TR05-017
Authors: Phong Nguyen
Publication: 4th February 2005 16:40
Downloads: 1785
Keywords: 


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.



ISSN 1433-8092 | Imprint