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.

_{=}L is that it has a nice complete problem: singular integer matrices. This is because for every GapL function f there is a log-space computable g mapping strings to integer matrices such that f(x) is the determinant of g(x).

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.

## No comments:

## Post a Comment