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

Anupam Das and Isabel Oitavem. Accepted to CSL '18. 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.