文章基本信息

标题：Listings and logics
本地全文：下载
作者：Yijia Chen, Joerg Flum
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 LFPinv, 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 DTCinv (TCinv). As a byproduct we get that LFPinv captures P if DTCinv 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.
关键词：Listing, Logic for Complexity Class, Space Optimal Algorithm