Tailoring recursion for complexity

DOI10.2307/2275767zbMath0837.03034MaRDI QIDQ4858828

Erich Grädel, Yuri Gurevich

Publication date: 19 December 1995

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2275767

zbMATH Keywords

polynomial time; finite model theory; complexity classes; descriptive complexity theory

Mathematics Subject Classification ID

03D15: Complexity of computation (including implicit computational complexity)

03C13: Model theory of finite structures

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Algebraic and logical characterizations of deterministic linear time classes, Implicit complexity over an arbitrary structure: Quantifier alternations, Intensional Properties of Polygraphs, Computational Complexity Via Finite Types

Cites Work

• Fixed-point extensions of first-order logic
• The method of forced enumeration for nondeterministic automata
• The complexity of optimization problems
• Upper and lower bounds for first order expressibility
• Datalog extensions for database queries and updates
• Capturing complexity classes by fragments of second-order logic
• An algebra and a logic for \(NC^ 1\)
• Weak Second‐Order Arithmetic and Finite Automata
• A logic for constant-depth circuits
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation