exponential time arithmetic

[martdowd at aol.com]

FOM:

I've been writing papers in set theory for a while.  I've put this aside
to write a complexity theory paper.  The vague idea was to develop
propositional representation theory for the Grzegorczyk hierarchy.
As I got started I found the 1986 reference
 "Exponential Time and Bounded Arithmetic"
by Clote and Takeuti, and decided to work on exponential time to begin with.
I have always liked equational theories better that bounded arithmetic,
so the first order of business was to develop an equational formulation
of exponential time arithmetic on top of polynomial time arithmetic
(which I learned thoroughly doing my PhD under Cook).

I intend to continue the research; since I have obtained an interesting
result already I am submitting a manuscript,
 "Equational Formal Systems for Iterated Exponential Arithmetic",
currently available at
 https://www.researchgate.net/publication/
  339130069_Equational_Formal_Systems_for_Iterated_Exponential_Arithmetic

The main result is that the consistence of polynomial time arithmetic is
provable in double exponential time arithmetic.  More generally the
consistency of k-fold exponential time arithmetic is provable in (k+2)-fold
exponential time arithmetic.  A 1967 result of Cleave and Rose in their
paper "En-arithmetic", is that the consistency of E2-arithmetic is provable
in E3-arithmetic.  It follows from my results that it is provable in triple
exponential time arithmetic.

If anyone knows of any relevant results in this area please send me an
email.  Also, the question is left open of whether there is an equation
in the language of polynomial time arithmetic which is not provable in
polynomial time arithmetic, but is provable in single exponential time
arithmetic.  If anyone answers this question please send me an email.

- Thanks, Martin Dowd
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20200208/70fa153a/attachment-0001.html>