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 language | English |
---|---|
Title of host publication | Computer Science Logic 2018, CSL 2018 |
Editors | Dan R. Ghica, Achim Jung |
Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
Number of pages | 1 |
Volume | 119 |
ISBN (Print) | 978-395977088-0 |
DOIs | |
Publication status | Published - 1 Aug 2018 |
Event | 27th Annual EACSL Conference Computer Science Logic, CSL 2018 - Birmingham, United Kingdom Duration: 4 Sept 2018 → 7 Sept 2018 |
Conference
Conference | 27th Annual EACSL Conference Computer Science Logic, CSL 2018 |
---|---|
Country/Territory | United Kingdom |
City | Birmingham |
Period | 4/09/18 → 7/09/18 |
Keywords
- Function algebras
- Function classes
- Implicit complexity
- Logic
- Monotone complexity
- Positive complexity
- Recursion-theoretic characterisations