4 citations · 4 across the 2 of their papers we have counts for
3 papers
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…
cs.LO2011★ 4 cited
An applicative theory for FPH
Reinhard Kahle, Isabel Oitavem
In this paper we introduce an applicative theory which characterizes the polynomial hierarchy of time.