Switch to: References

Add citations

You must login to add citations.
  1. Iterated multiplication in $$ VTC ^0$$.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
    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 (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Iterated multiplication in $$ VTC ^0$$ V T C 0.Emil Jeřábek - 2022 - Archive for Mathematical Logic 61 (5):705-767.
    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 (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations