Institut de Mathématiques de Luminy

Abstract 2001-07

Lafont Yves.
Soft linear logic and polynomial time


We present a subsystem of second order Linear Logic with restricted rules for exponentials so that proofs correspond to polynomial time algorithms, and vice-versa.

 

 



Last update : april 2, 2001, EL.