The most nonelementary theory (Q598194)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The most nonelementary theory |
scientific article; zbMATH DE number 2083126
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | The most nonelementary theory |
scientific article; zbMATH DE number 2083126 |
Statements
The most nonelementary theory (English)
0 references
6 August 2004
0 references
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.
0 references
lower complexity bound
0 references
nonelementary theory
0 references
generic reduction
0 references
inductive definition
0 references
0 references
0 references
0 references
0 references
0.7689972
0 references
0 references
