Consistency of polynomial space arithmetic

[martdowd at aol.com]

FOM,

As a follow-up on my last post, the proof of theorem 57 of
 https://www.researchgate.net/publication/347944185
can be strengthened, to show that the consistency of polynomial space
arithmetic can be proved in double exponential time arithmetic.

Basically, the space bound for the automaton doesn't change, and the
time bound is multiplied by a single exponential factor.

This is an improvement over Cleave and Rose 1967.

Martin Dowd

-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20201231/4cb46fb8/attachment.html>