论文标题
迭代乘法在$ VTC^0 $中
Iterated multiplication in $VTC^0$
论文作者
论文摘要
我们表明，$ vtc^0 $，有限算术的基本理论，对应于复杂性类别$ \ mathrm {tc}^0 $，证明了$ imul $ axiom表达迭代倍数的全部乘以其递归定义的整体，并通过正式的版本的形式化了$ \ mathrm的适当版本，该版本是由$ \ mathrm {mathrm {tc}^0 $ {0 $ {0 $ {0 $ {0 $ {0 $ {巴灵顿。结果，$ vtc^0 $也可以证明整数划分公理，并且（通过我们先前的结果）启动和最小化的RSUV转换对急剧有限的公式。相关理论的类似后果$δ^b_1 $ - $ cr $和$ c^0_2 $。 作为综上的结果，我们还证明，在$iΔ_0+wphp（δ_0）$中，$δ_0$的$δ_0$定义。
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 $Δ^b_1$-$CR$ and $C^0_2$. As a side result, we also prove that there is a well-behaved $Δ_0$ definition of modular powering in $IΔ_0+WPHP(Δ_0)$.
