Paths-based criteria and application to linear logic subsystems characterizing polynomial time

Matthieu Perrinel

Several variants of linear logic have been proposed to characterize complexity classes in the proofs-as-programs correspondence. Light linear logic (LLL) ensures a polynomial bound…