2026-07-23T07:57:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5170 2024-03-06T10:36:11Z ddc:004 open_access

Polynomial Time in the Parametric Lambda Calculus Redmond, Brian F. Parametric Lambda Calculus Polynomial Time Complexity Combinators Nondeterminism and Explicit Products Implicit Computational Complexity In this paper we investigate Implicit Computational Complexity via the parametric lambda calculus of Ronchi Della Rocca and Paolini. We show that a particular instantiation of the set of input values leads to a characterization of polynomial time computations in a similar way to Lafont’s Soft Linear Logic. This characterization is manifestly type-free and does not require any ad hoc extensions to the pure lambda calculus. Moreover, there is a natural extension to nondeterminism with the addition of explicit products. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Brian F. Redmond 2015 Is Part Of LIPIcs, Volume 38, 13th International Conference on Typed Lambda Calculi and Applications (TLCA 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TLCA.2015.288 urn:nbn:de:0030-drops-51705 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TLCA.2015.288 eng https://creativecommons.org/licenses/by/3.0/legalcode