2 papers
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.LO2014
Logic Programming and Logarithmic Space
Clément Aubert, Marc Bagnol, Paolo Pistone +1
We present an algebraic view on logic programming, related to proof theory and more specifically linear logic and geometry of interaction. Within this construction, a characterizat…