Elementary analytic functions in $VT{C}^0$

Abstract

It is known that rational approximations of elementary analytic functions (exp, log, trigonometric, and hyperbolic functions, and their inverse functions) are computable in the weak complexity class ${\mathrm{TC}}^0$. We show how to formalize the construction and basic properties of these functions in the corresponding theory of bounded arithmetic, ${\mathsf{VTC}}^0$.

57 pages

References in corpus (1)

• Open induction in a bounded arithmetic for TC^0

Cited by in corpus (2)

• Quantum Automating ${\mathbf{TC}}^0$-Frege Is LWE-Hard
• Models of $VT{C}^0$ as exponential integer parts