On Sharing, Memoization, and Polynomial Time (Long Version)

Martin Avanzini, Ugo Dal Lago

We study how the adoption of an evaluation mechanism with sharing and memoization impacts the class of functions which can be computed in polynomial time. We first show how a natur…