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  
  • Abelian groups and quadratic residues in weak arithmetic.Emil Jeřábek - 2010 - Mathematical Logic Quarterly 56 (3):262-278.
    We investigate the provability of some properties of abelian groups and quadratic residues in variants of bounded arithmetic. Specifically, we show that the structure theorem for finite abelian groups is provable in S22 + iWPHP, and use it to derive Fermat's little theorem and Euler's criterion for the Legendre symbol in S22 + iWPHP extended by the pigeonhole principle PHP. We prove the quadratic reciprocity theorem in the arithmetic theories T20 + Count2 and I Δ0 + Count2 with modulo-2 counting (...)
    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