Probabilistic Soft Type Assignment

Gianluca Curzi, Luca Roversi

We model randomized complexity classes in the style of Implicit Computational Complexity. We introduce PSTA, a probabilistic version of STA, the type-theoretical counterpart of Sof…