A recursion-theoretic characterisation of the positive polynomial-time functions

Anupam Das and Isabel Oitavem. In proceedings of CSL '18. (Invited to special issue). DOI PDF

We extend work of Lautemann, Schwentick and Stewart on characterisations of the ‘positive’ polynomial-time predicates (posP, also called mP by Grigni and Sipser) to function classes. Our main result is the obtention of a function algebra for the positive polynomial-time functions (posFP), by imposing a simple uniformity condition on the bounded recursion operator in Cobham’s characterisation of FP. We also observe that the tally sets of posP are precisely the unary codings of LINSPACE predicates.