Open induction in a bounded arithmetic for TC^0

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F15%3A00442879" target="_blank" >RIV/67985840:_____/15:00442879 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/s00153-014-0414-7" target="_blank" >http://dx.doi.org/10.1007/s00153-014-0414-7</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/s00153-014-0414-7" target="_blank" >10.1007/s00153-014-0414-7</a>

Result language
angličtina
Original language name
Open induction in a bounded arithmetic for TC^0
Original language description
The elementary arithmetic operations ... on integers are well-known to be computable in the weak complexity class TC0, and it is a basic question what properties of these operations can be proved using only TC0-computable objects, i.e., in a theory of bounded arithmetic corresponding to TC0. We will show that the theory VTC 0 extended with an axiom postulating the totality of iterated multiplication (which is computable in TC0) proves induction for quantifier-free formulas in the language ... (IOpen), and more generally, minimization for ... b 0 formulas in the language of Buss?s S 2.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)