Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426377 | Information and Computation | 2016 | 20 Pages |
Abstract
In a recent work, Girard proposed a new and innovative approach to computational complexity based on the proofs-as-programs correspondence. In a previous paper, the authors showed how Girard's proposal succeeds in obtaining a new characterization of co-NL languages as a set of operators acting on a Hilbert Space. In this paper, we extend this work by showing that it is also possible to define a set of operators characterizing the class L of logarithmic space languages.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Clément Aubert, Thomas Seiller,