Sometimes a class that seems a mix of concepts turns out to have significant meaning. C=L is one of these classes. First we need to define the class.
Consider a nondeterministic log-space Turing machine M that never repeats a configuration. This is not much of a restriction since we can just add a clock to the machine. Let #L be the set of functions such that f(x) is the number of accepting paths of M(x) for some M as described above. Let GapL be the closure of #L under subtraction.
We say a language L is in C=L if there exists
a function f in GapL such that for all x, x is in L if and only if f(x)=0. (*)
C=L is the log-space equivalent of the counting class C=P. There are many equivalent definitions to C=L where we can replace (*) by
- A function f in GapL and a function log-space computable function g such that for all x, x is in L if and only if f(x)=g(x).
- A function f in #L and a log-space computable function g such that for all x, x is in L if and only if f(x)=g(x).
- A probabilistic log-space machine M such that x is in L if and only if Pr(M(x) accepts) = 1/2.
The big open question about C=L is whether it is closed under complement, i.e., is there a log-space computable function g mapping matrices to matrices such that M is singular if and only if g(M) is nonsingular?
For more information about C=L and related classes including references and proofs of the above see the paper of Eric Allender and Mitsu Ogihara, Relationships among PL, #L, and the Determinant, RAIRO - Theoretical Informatics and Applications Vol. 30, 1996, pp. 1-21.
Post a Comment