Showing 2023Show all
2 papers · 1 filter
cs.LO2023
Enumerating Error Bounded Polytime Algorithms Through Arithmetical Theories
Melissa Antonelli, Ugo Dal Lago, Davide Davoli +2
We consider a minimal extension of the language of arithmetic, such that the bounded formulas provably total in a suitably-defined theory à la Buss (expressed in this new language)…
cs.CC2023
An Arithmetic Theory for the Poly-Time Random Functions
Melissa Antonelli, Ugo Dal Lago, Davide Davoli +2
We introduce a new bounded theory RS^1_2 and show that the functions which are Sigma^b_1-representable in it are precisely random functions which can be computed in polynomial time…