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

Anupam Das, Isabel Oitavem

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

14 Downloads (Pure)

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 publication27th EASCL Annual Conference on Computer Science Logic 2018 (CSL 2018)
EditorsDan R. Ghica, Achim Jung
PublisherSchloss Dagstuhl
Number of pages17
ISBN (Print)9783959770880
DOIs
Publication statusPublished - 1 Aug 2018
Event27th Annual EACSL Conference Computer Science Logic, CSL 2018 - Birmingham, United Kingdom
Duration: 4 Sep 20187 Sep 2018

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume119
ISSN (Print)1868-8969

Conference

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

Keywords

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

ASJC Scopus subject areas

  • Software

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