Linear Logic & Polynomial Time
Damiano Mazza · 2006
Light and Elementary Linear Logic, the cornerstones at the interface between logic and implicit computational complexity, were originally introduced by Girard as “stand-alone” logical systems with a (somewhat awkward) sequent calculus of their own. The latter has later been reformulated by Danos and Joinet as a proper subsystem of linear logic, whose proofs satisfy a certain structural condition. We extend this approach to polytime computation, finding two solutions: the first one, obtained by a simple extension of DanosJ the second one, which needs more complex conditions, exactly corresponds to Girard’s Light Linear Logic.