We show that $$ VTC ^0$$, the basic theory of bounded arithmetic corresponding to the complexity class $$\mathrm {TC}^0$$, proves the $$ IMUL $$ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the $$\mathrm {TC}^0$$ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, $$ VTC ^0$$ can also prove the integer division axiom, and (by our previous results) the $$ RSUV $$ -translation of induction and minimization for sharply (...) bounded formulas. Similar consequences hold for the related theories $$\Delta ^b_1\text{- } CR $$ and $$C^0_2$$. As a side result, we also prove that there is a well-behaved $$\Delta _0$$ definition of modular powering in $$I\Delta _0+ WPHP (\Delta _0)$$. (shrink)

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1 + ¬Ω1has a proper end-extension to a model of Π1, and so Π1 + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1 + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1 by IΔ0as the base theory.We also show that any proof that IΔ0+ ¬Exp does not (...) prove a given finite fragment of BΣ1has to be “nonrelativizing”, in the sense that it will not work in the presence of an arbitrary oracle. (shrink)

The use of $Nepomnja\check{s}\check{c}i\check{i}'s$ Theorem in the proofs of independence results for bounded arithmetic theories is investigated. Using this result and similar ideas, it is shown that at least one of S1 or TLS does not prove the Matiyasevich-Robinson-Davis-Putnam Theorem. It is also established that TLS does not prove a statement that roughly means nondeterministic linear time is equal to co-nondeterministic linear time. Here S1 is a conservative extension of the well-studied theory IΔ0 and TLS is a theory for LOGSPACE (...) reasoning. (shrink)

We show that \, the basic theory of bounded arithmetic corresponding to the complexity class \, proves the \ axiom expressing the totality of iterated multiplication satisfying its recursive definition, by formalizing a suitable version of the \ iterated multiplication algorithm by Hesse, Allender, and Barrington. As a consequence, \ can also prove the integer division axiom, and the \-translation of induction and minimization for sharply bounded formulas. Similar consequences hold for the related theories \ and \. As a side (...) result, we also prove that there is a well-behaved \ definition of modular powering in \\). (shrink)

We prove that: • if there is a model of I∆₀ + ¬ exp with cofinal Σ₁-definable elements and a Σ₁ truth definition for Σ₁ sentences, then I∆₀ + ¬ exp +¬BΣ₁ is consistent, • there is a model of I∆₀ Ω₁ + ¬ exp with cofinal Σ₁-definable elements, both a Σ₂ and a ∏₂ truth definition for Σ₁ sentences, and for each n > 2, a Σ n truth definition for Σ n sentences. The latter result is obtained by (...) constructing a model with a recursive truth-preserving translation of Σ₁ sentences into boolean combinations of $\exists \sum {\begin{array}{*{20}{c}} h \\ 0 \\ \end{array} } $ sentences. We also present an old but previously unpublished proof of the consistency of I∆₀ + ¬ exp + ¬BΣ₁ under the assumption that the size parameter in Lessan's ∆₀ universal formula is optimal. We then discuss a possible reason why proving the consistency of I∆₀ + ¬ exp + ¬BΣ₁ unconditionally has turned out to be so difficult. (shrink)