The most nonelementary theory
type: Item
instance of: scholarly article
title: The most nonelementary theory
zbMATH Open document ID: 1064.03029
author: Sergei Vorobyov
published in: Information and Computation
publication date: 2004-08-06T00:00:00Z
review text: The author affirmatively settles the following problem [\textit{K. J. Compton} and \textit{C. W. Henson}, Ann. Pure Appl. Logic 48, 1--79 (1990; Zbl 0705.03017)]: ``Is there a `natural' decidable theory with a lower bound of the form \(\exp_\infty(f(n))\), where \(f\) is not linearly bounded?'' The author proves that testing the validity of formulas in a decidable rudimentary theory of finite typed sets requires such a lower bound.
Mathematics Subject Classification ID: 03D15
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 2083126
zbMATH Keywords: lower complexity bound
zbMATH Keywords: nonelementary theory
zbMATH Keywords: generic reduction
zbMATH Keywords: inductive definition
reviewed by: M. M. Arslanov
MaRDI profile type: Publication
full work available at URL: j.ic.2004.02.002
OpenAlex ID: W2129501349
cites work: A uniform method for proving lower bounds on the computational complexity of logical theories
cites work: The computational complexity of logical theories
cites work: A theory of prepositional types
cites work: Q3862379
cites work: On the expressive power of database queries with intermediate types
cites work: On the complexity of queries in the logical data model
cites work: Complexity results for classes of quantificational formulas
cites work: A simple proof of a theorem of Statman
cites work: Q4133967
cites work: Q4090322
cites work: The typed lambda-calculus is not elementary recursive
cites work: Q4131648
cites work: The polynomial-time hierarchy
cites work: Classifying the computational complexity of problems
DOI: 10.1016/J.IC.2004.02.002
Recommended article: Nonelementary catastrophe theory
Recommended article: An infinite element theory
Recommended article: The most irrational rational theories
Recommended article: Non-totally transcendental unidimensional theories
Recommended article: Q3629232
Recommended article: Q3257596
Recommended article: Strongly nonmultidimensional theories
Recommended article: Q4249357
Recommended article: Q4884543
description: scientific article; zbMATH DE number 2083126