Computational Complexity

Wednesday, September 18, 2002

 
Complexity Class of the Week: C₌L

Posted by Lance

Previous CCW

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

1. 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).
2. 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).
3. A probabilistic log-space machine M such that x is in L if and only if Pr(M(x) accepts) = 1/2.

The neat part of C₌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.

4:25 PM # 0 comments

Comment Feeds: This Post All