The most nonelementary theory

DOI10.1016/j.ic.2004.02.002zbMath1064.03029OpenAlexW2129501349MaRDI QIDQ598194

Sergei Vorobyov

Publication date: 6 August 2004

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2004.02.002

zbMATH Keywords

lower complexity boundinductive definitiongeneric reductionnonelementary theory

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

THE RECOGNITION COMPLEXITY OF DECIDABLE THEORIES ⋮ Complexity Hierarchies beyond Elementary

Cites Work

• On the complexity of queries in the logical data model
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Complexity results for classes of quantificational formulas
• On the expressive power of database queries with intermediate types
• A simple proof of a theorem of Statman
• The polynomial-time hierarchy
• The computational complexity of logical theories
• The typed lambda-calculus is not elementary recursive
• Classifying the computational complexity of problems
• A theory of prepositional types
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The most nonelementary theory