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

Anupam Das, Isabel Oitavem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We extend work of Lautemann, Schwentick and Stewart [14] on characterisations of the "positive" polynomial-time predicates (posP, also called mP by Grigni and Sipser [11]) 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 constraint on the bounded recursion operator in Cobham's characterisation of FP. We show that a similar constraint on a function algebra based on safe recursion, in the style of Bellantoni and Cook [3], yields an "implicit" characterisation of posFP, mentioning neither explicit bounds nor explicit monotonicity constraints.

Original languageEnglish
Title of host publicationComputer Science Logic 2018, CSL 2018
EditorsDan R. Ghica, Achim Jung
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages1
Volume119
ISBN (Print)978-395977088-0
DOIs
Publication statusPublished - 1 Aug 2018
Event27th Annual EACSL Conference Computer Science Logic, CSL 2018 - Birmingham, United Kingdom
Duration: 4 Sep 20187 Sep 2018

Conference

Conference27th Annual EACSL Conference Computer Science Logic, CSL 2018
CountryUnited Kingdom
CityBirmingham
Period4/09/187/09/18

Keywords

  • Function algebras
  • Function classes
  • Implicit complexity
  • Logic
  • Monotone complexity
  • Positive complexity
  • Recursion-theoretic characterisations

Fingerprint Dive into the research topics of 'A recursion-theoretic characterisation of the positive polynomial-time functions'. Together they form a unique fingerprint.

  • Cite this

    Das, A., & Oitavem, I. (2018). A recursion-theoretic characterisation of the positive polynomial-time functions. In D. R. Ghica, & A. Jung (Eds.), Computer Science Logic 2018, CSL 2018 (Vol. 119). [18] Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.CSL.2018.18