[Proof Complexity] preprint

[Emil Jerabek]

Dear colleagues,

I've uploaded an updated version of the paper, with an extension of
the main result to \Sigma^b_0 formulas in Buss's language.

Best regards,
Emil Jerabek


On Tue, Apr 29, 2014 at 06:55:51PM +0200, Emil Jerabek wrote:
> 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
> _______________________________________________
> Proof-Complexity mailing list
> Proof-Complexity at math.cas.cz
> http://list.math.cas.cz/listinfo/proof-complexity