2026-07-23T15:54:50Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9685 2024-03-06T10:44:49Z ddc:004 open_access

A Recursion-Theoretic Characterisation of the Positive Polynomial-Time Functions Das, Anupam Oitavem, Isabel Monotone complexity Positive complexity Function classes Function algebras Recursion-theoretic characterisations Implicit complexity Logic We extend work of Lautemann, Schwentick and Stewart [Clemens Lautemann et al., 1996] on characterisations of the "positive" polynomial-time predicates (posP, also called mP by Grigni and Sipser [Grigni and Sipser, 1992]) 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 [Stephen Bellantoni and Stephen A. Cook, 1992], yields an "implicit" characterisation of posFP, mentioning neither explicit bounds nor explicit monotonicity constraints. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anupam Das and Isabel Oitavem 2018 Is Part Of LIPIcs, Volume 119, 27th EACSL Annual Conference on Computer Science Logic (CSL 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2018.18 urn:nbn:de:0030-drops-96851 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2018.18 eng https://creativecommons.org/licenses/by/3.0/legalcode