Descriptive characterizations of computational complexity

DOI10.1016/0022-0000(89)90019-6zbMath0677.68045OpenAlexW2079745007MaRDI QIDQ1123616

Daniel Leivant

Publication date: 1989

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(89)90019-6

zbMATH Keywords

descriptive complexitylogical characterizationof complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (16)

How Hard Is Positive Quantification? ⋮ Expressiveness of Logic Programs under the General Stable Model Semantics ⋮ Computing queries with higher-order logics ⋮ How to define a linear order on finite models ⋮ Normal forms for second-order logic over finite structures, and classification of NP optimization problems ⋮ A computational model for generic graph functions ⋮ The Expressive Power of Higher-Order Datalog ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ Computing on structures ⋮ Capturing complexity classes by fragments of second-order logic ⋮ Computable Queries for Object Oriented Databases ⋮ On the expressiveness of frame satisfiability and fragments of second-order logic ⋮ Expressibility of Higher Order Logics ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ The Descriptive Complexity of the Deterministic Exponential Time Hierarchy ⋮ Reflective relational machines

Cites Work

• Henkin quantifiers and complete problems
• Computable queries for relational data bases
• Number of quantifiers is better than number of tape cells
• The polynomial-time hierarchy
• On non-determinacy in simple computing devices
• A programming language for the inductive sets, and applications
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Second-order and Inductive Definability on Finite Structures
• Alternation
• Global inductive definability
• Turing machines and the spectra of first-order formulas
• Metarecursive sets
• Applications of Strict Π₁¹ predicates to infinitary logic
• Finite partially-ordered quantification
• The next admissible set
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Descriptive characterizations of computational complexity