6533b870fe1ef96bd12cf958

RESEARCH PRODUCT

Descriptive Complexity, Lower Bounds and Linear Time

Thomas Schwentick

subject

Computational complexity theoryComputer scienceDescriptive complexity theoryMathematical proofCombinatoricsTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESRegular languageCalculusComplexity classsymbolsUnary functionTime complexity

description

This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of logics.

yearjournalcountryeditionlanguage
1999-01-01
https://doi.org/10.1007/10703163_2