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…