Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOGIC FOR COMPLEXITY CLASS:
Reports tagged with Logic for Complexity Class:
TR11-020 | 20th December 2010
Yijia Chen, Joerg Flum

Listings and logics

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 ... more >>>




ISSN 1433-8092 | Imprint