Descriptive characterizations of computational complexity
From MaRDI portal
Several complexity classes, such as Nlog-Space, P-Time, P-Space, and Exp- Time are characterized in terms of formulas of the form (\(\forall\) relations) (\(\exists\) objects) \(\phi\) with \(\phi\) quantifier-free. Different syntactic variants of such formulas characterize different complexity classes. In particular, such descriptive characterizations in terms of higher order logical formulas are considered.
Recommendations
Cites work
- A programming language for the inductive sets, and applications
- Alternation
- Applications of Strict Π11 predicates to infinitary logic
- Computable queries for relational data bases
- Finite partially-ordered quantification
- Global inductive definability
- Henkin quantifiers and complete problems
- scientific article; zbMATH DE number 3885864 (Why is no real title available?)
- scientific article; zbMATH DE number 3122413 (Why is no real title available?)
- scientific article; zbMATH DE number 3857078 (Why is no real title available?)
- scientific article; zbMATH DE number 3685474 (Why is no real title available?)
- scientific article; zbMATH DE number 3474957 (Why is no real title available?)
- scientific article; zbMATH DE number 3494394 (Why is no real title available?)
- scientific article; zbMATH DE number 3548469 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3349781 (Why is no real title available?)
- scientific article; zbMATH DE number 3196255 (Why is no real title available?)
- scientific article; zbMATH DE number 3076636 (Why is no real title available?)
- Languages that Capture Complexity Classes
- Metarecursive sets
- Number of quantifiers is better than number of tape cells
- On non-determinacy in simple computing devices
- Relational queries computable in polynomial time
- Second-order and Inductive Definability on Finite Structures
- The next admissible set
- The polynomial-time hierarchy
- Turing machines and the spectra of first-order formulas
Cited in
(35)- Uniform normal form for general time-bounded complexity classes
- Capturing complexity classes by fragments of second-order logic
- The quantifier structure of sentences that characterize nondeterministic time complexity
- Reflective relational machines
- Logical and schematic characterization of complexity classes
- How to define a linear order on finite models
- A second-order system for polytime reasoning based on Grädel's theorem.
- Arithmetical definability and computational complexity
- Normal forms for second-order logic over finite structures, and classification of NP optimization problems
- Descriptive complexity of deterministic polylogarithmic time
- Computing queries with higher-order logics
- Descriptional complexity and operations -- two non-classical cases
- Descriptive complexity of deterministic polylogarithmic time and space
- Characterizing small depth and small space classes by operators of higher types
- Structure and specification as sources of complexity
- scientific article; zbMATH DE number 4130360 (Why is no real title available?)
- The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
- Languages that Capture Complexity Classes
- scientific article; zbMATH DE number 17544 (Why is no real title available?)
- scientific article; zbMATH DE number 1342206 (Why is no real title available?)
- On the Computational Complexity of Small Descriptions
- scientific article; zbMATH DE number 1072527 (Why is no real title available?)
- On the expressiveness of frame satisfiability and fragments of second-order logic
- scientific article; zbMATH DE number 1978903 (Why is no real title available?)
- scientific article; zbMATH DE number 1540059 (Why is no real title available?)
- Computing on structures
- Computable queries for object oriented databases
- Expressibility of higher order logics
- scientific article; zbMATH DE number 1424025 (Why is no real title available?)
- A computational model for generic graph functions
- The expressive power of higher-order Datalog
- The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
- How hard is positive quantification?
- Expressiveness of logic programs under the general stable model semantics
- Syntactic characterizations of polynomial time optimization classes
This page was built for publication: Descriptive characterizations of computational complexity
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1123616)
