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

Anupam Das; Isabel Oitavem

doi:10.4230/LIPIcs.CSL.2018.18

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

Anupam Das, Isabel Oitavem

DM - Departamento de Matemática

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Citation (Scopus)

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	https://doi.org/10.4230/LIPIcs.CSL.2018.18
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

Access to Document

10.4230/LIPIcs.CSL.2018.18Licence: Unspecified

Cite this

@inproceedings{fbbdc220067845a2adfaae065f3f30d8,

title = "A recursion-theoretic characterisation of the positive polynomial-time functions",

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.",

keywords = "Function algebras, Function classes, Implicit complexity, Logic, Monotone complexity, Positive complexity, Recursion-theoretic characterisations",

author = "Anupam Das and Isabel Oitavem",

note = "Sem pdf; 27th Annual EACSL Conference Computer Science Logic, CSL 2018 ; Conference date: 04-09-2018 Through 07-09-2018",

year = "2018",

month = aug,

day = "1",

doi = "10.4230/LIPIcs.CSL.2018.18",

language = "English",

isbn = "978-395977088-0",

volume = "119",

editor = "Ghica, {Dan R.} and Achim Jung",

booktitle = "Computer Science Logic 2018, CSL 2018",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

}

Das, A & Oitavem, I 2018, A recursion-theoretic characterisation of the positive polynomial-time functions. in DR Ghica & A Jung (eds), Computer Science Logic 2018, CSL 2018. vol. 119, 18, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 27th Annual EACSL Conference Computer Science Logic, CSL 2018, Birmingham, United Kingdom, 4/09/18. https://doi.org/10.4230/LIPIcs.CSL.2018.18

A recursion-theoretic characterisation of the positive polynomial-time functions. / Das, Anupam; Oitavem, Isabel.
Computer Science Logic 2018, CSL 2018. ed. / Dan R. Ghica; Achim Jung. Vol. 119 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018. 18.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Das, Anupam

AU - Oitavem, Isabel

N1 - Sem pdf

PY - 2018/8/1

Y1 - 2018/8/1

N2 - 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.

AB - 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.

KW - Function algebras

KW - Function classes

KW - Implicit complexity

KW - Logic

KW - Monotone complexity

KW - Positive complexity

KW - Recursion-theoretic characterisations

UR - http://www.scopus.com/inward/record.url?scp=85053057954&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CSL.2018.18

DO - 10.4230/LIPIcs.CSL.2018.18

M3 - Conference contribution

AN - SCOPUS:85053057954

SN - 978-395977088-0

VL - 119

BT - Computer Science Logic 2018, CSL 2018

A2 - Ghica, Dan R.

A2 - Jung, Achim

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 27th Annual EACSL Conference Computer Science Logic, CSL 2018

Y2 - 4 September 2018 through 7 September 2018

ER -

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

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this