Logarithmic Space and Permutations

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 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.

References in corpus (3)

• Multi-Head Finite Automata: Characterizations, Concepts and Open Problems
• Characterizing co-NL by a group action
• Sublogarithmic uniform Boolean proof nets

Cited by in corpus (8)

• Towards a Complexity-through-Realisability Theory
• Interaction Graphs: Exponentials
• Interaction Graphs: Graphings
• A Correspondence between Maximal Abelian Sub-Algebras and Linear Logic Fragments
• Memoization for Unary Logic Programming: Characterizing PTIME
• Probabilistic Complexity Classes through Semantics
• Interaction Graphs: Additives
• An in-between "implicit" and "explicit" complexity: Automata