@inproceedings{fbfca0822e354abba4ad3cfd24de0a0b,
title = "Non-uniform polytime computation in the infinitary affine lambda-calculus",
abstract = "We give an implicit, functional characterization of the class of non-uniform polynomial time languages, based on an infinitary affine lambda-calculus and on previously defined bounded-complexity subsystems of linear (or affine) logic. The fact that the characterization is implicit means that the complexity is guaranteed by structural properties of programs rather than explicit resource bounds. As a corollary, we obtain a proof of the (already known) P-completeness of the normalization problem for the affine lambda-calculus which mimics in an interesting way Ladner's P-completeness proof of CIRCUIT VALUE (essentially, the argument giving the Cook-Levin theorem). This suggests that the relationship between affine and usual lambda-calculus is deeply similar to that between Boolean circuits and Turing machines.",
author = "Damiano Mazza",
year = "2014",
month = jan,
day = "1",
doi = "10.1007/978-3-662-43951-7\_26",
language = "English",
isbn = "9783662439500",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
number = "PART 2",
pages = "305--317",
booktitle = "Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Proceedings",
edition = "PART 2",
note = "41st International Colloquium on Automata, Languages, and Programming, ICALP 2014 ; Conference date: 08-07-2014 Through 11-07-2014",
}