Soft Linear Logic and Polynomial Complexity Classes

Marco Gaboardi (1) , Jean-Yves Marion (2) , Simona Ronchi Della Rocca (1)

1 Dipartimento di Informatica [Torino]
2 CARTE - Theoretical adverse computations, and safety

We describe some results inspired to Lafont's Soft Linear Logic (SLL) which is a subsystem of second-order linear logic with restricted rules for exponentials, correct and complete for polynomial time computations. SLL is the basis for the design of type assignment systems for lambda-calculus, characterizing the complexity classes PTIME, PSPACE and NPTIME. PTIME is characterized by a type assignments system where types are a proper subset of SLL formulae. The characterization consists in the fact that a well typed term can be reduced to normal form by a number of beta-reductions polynomial in its lenght, and moreover all polynomial time functions can be computed by well typed terms. PSPACE is characterized by a type assignment system obtained from the previous one, by extending the set of types by a type for booleans, and the lambda-calculus by two boolean constants and a conditional constructor. The system assigns types to terms in such a way that the evaluation of programs (closed terms of type boolean) can be performed carefully in polynomial space. Moreover all polynomial space decision problems can be computed by terms typable in this system. In order to characterize NPTIME we extend the lambda-calculus by a nondeterministic choice operator, and the system by a rule for dealing with this new term constructor.

Mots clés: Implicit computational complexity; linear logic; polynomial space; type assignment

Domaines: Logique en informatique [cs.LO]

Marco Gaboardi, Jean-Yves Marion, Simona Ronchi Della Rocca. Soft Linear Logic and Polynomial Complexity Classes. Electronic Notes in Theoretical Computer Science, 2008, 205 (6), pp.67-87. ⟨10.1016/j.entcs.2008.03.066⟩. ⟨hal-00342320⟩