Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR11-020 | 20th December 2010 09:42

Listings and logics


Authors: Yijia Chen, Joerg Flum
Publication: 11th February 2011 11:57
Downloads: 2662


There are standard logics DTC, TC, and LFP capturing the complexity classes L, NL, and P on ordered structures, respectively. In [Chen and Flum, 2010] we have shown that ${\rm LFP}_{\rm inv}$, the ``order-invariant least fixed-point logic LFP,'' captures P (on all finite structures) if and only if there is a listing of the P-subsets of the set TAUT of propositional tautologies. By a thorough analysis of this relationship between listings and logics we are able to extend the result to listings of the L-subsets (NL-subsets) of TAUT and the logic ${\rm DTC}_{\rm inv}$ (${\rm TC}_{\rm inv}$). As a byproduct we get that ${\rm LFP}_{\rm inv}$ captures P if ${\rm DTC}_{\rm inv}$ captures L.

Furthermore, we show that the existence of a listing of the L-subsets of TAUT is equivalent to the existence of an almost space optimal algorithm for TAUT. To obtain this result we have to derive a space version of a theorem of Levin on optimal inverters.

ISSN 1433-8092 | Imprint