[Proof Complexity] preprint

[Emil Jerabek]

Dear colleagues,

A new preprint, "Open induction in a bounded arithmetic for TC^0", is
available on my web page (http://math.cas.cz/~jerabek). Comments,
corrections and suggestions are welcome.

Abstract:
The elementary arithmetic operations +,\cdot,\le on integers are
well-known to be computable in the weak complexity class TC^0, and it
is a basic question what properties of these operations can be proved
using only TC^0-computable objects, i.e., in a theory of bounded
arithmetic corresponding to TC^0. We will show that induction for
quantifier-free formulas in the language \langle +,\cdot,\le \rangle
(IOpen) is provable in the theory VTC^0 extended with an axiom
postulating the totality of iterated multiplication (which is
computable in TC^0).

Best regards,
Emil Jerabek