A recursion-theoretic characterisation of the positive polynomial-time functions
Authors: Anupam Das and Isabel Oitavem
Paper Information
| Title: | A recursion-theoretic characterisation of the positive polynomial-time functions |
| Authors: | Anupam Das and Isabel Oitavem |
| Proceedings: | LCC Contributed Talks |
| Editors: | Erich Grädel and Jan Hoffmann |
| Keywords: | Monotone complexity, Positive complexity, Function classes, Function algebras, Recursion-theoretic characterisations, Implicit complexity, Logic |
| Abstract: | ABSTRACT. We extend work of Lautemann, Schwentick and Stewart '96 on characterisations of the 'positive' polynomial-time predicates (posP, also called mP by Grigni and Sipser '92) 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. |
| Pages: | 5 |
| Talk: | Jul 13 11:15 (Session 86F: LCC: Contributed Talks) |
| Paper: |  |