A first link between formal arithmetic and complexity was provided by Cobham’s (1965) original characterization of \(\textbf{FP}\) in terms of a functional algebra similar to that by which the primitive recursive functions are defined. The class in question is generated by the following class of basis functions \(\mathcal{F}_0\):