
The paper under review is a contribution to the search for syntactically simple theories, without explicitely imposed bounds on quantifiers, whose provably recursive functions form ``more feasible'' complexity classes. A quite different, alternative treatment of Leivant's results is developed. The characterization is extended to the first level of exponential complexity in the hierarchy between Grzegorczyk's \(E^{2}\) and \(E^{3}\). The emphasis is on cut elimination in ``traditional'' theories based on unary numerals, so complexity in the end is measured in terms of the numerical input itself rather than its binary length.
First-order arithmetic and fragments, Complexity of computation (including implicit computational complexity), syntactically simple theories, Logic, Cut-elimination and normal-form theorems, provably recursive functions, cut elimination, Recursive functions and relations, subrecursive hierarchies, complexity classes
First-order arithmetic and fragments, Complexity of computation (including implicit computational complexity), syntactically simple theories, Logic, Cut-elimination and normal-form theorems, provably recursive functions, cut elimination, Recursive functions and relations, subrecursive hierarchies, complexity classes
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
