Structure and Importance of Logspace-MOD-Classes^{∗}

Gerhard Buntrock^{†}  Carsten Damm^{‡}

Ulrich Hertrampf^{†} Christoph Meinel^{‡}

Abstract. We refine the techniques of Beigel, Gill, Hertrampf [4] who investigated polynomial time counting classes, in order to make them applicable to the case of logarithmic space. We define the complexity classes MOD_{k}L and demonstrate their significance by proving that all standard problems of linear algebra over the finite rings Z/kZ are complete for these classes. We then define new complexity classes LogFew and LogFewNL and identify them as adequate logspace versions of Few and FewP. We show that LogFewNL is contained in MODZ_{k}L and that LogFew is contained in MOD_{k}L for all k. Also an upper bound for L^{#L} in terms of computation of integer determinants is given from which we conclude that all logspace counting classes are contained in the class DET , which was defined by Cook in [9].

1 Introduction

Valiant [19] defined the class #P of functions f such that there is a nondeterministic polynomial time Turing machine which, on input x, has exactly f(x) accepting computation paths. Many complexity classes in the area between P and PSPACE can be defined by a condition on f(x), for example, NP is the class of sets A such that there is a function f in #P with x ∈ A ⟺ f(x) > 0. For a good survey see [10] or [17]. In analogy to this Àlvarez and Jenner [2] introduced #L as the class of functions f, such that there is a nondeterministic logspace Turing machine which, on input x, has exactly f(x) accepting computation paths. Now the above characterization of NP becomes a characterization of NL, if we take f ∈ #L instead of f ∈ #P.

Other interesting classes which can be defined via #L are MOD_{k}L-classes, where the condition is: x ∈ A ⟺ f(x) ≢ 0 mod k. In [2] it is proved that #L ⊆ N C^{2}. We improve their result and show in Section 2 that L^{#L} is contained in DET , the class of problems which are N C^{1}-reducible to the computation of integer determinants (cf. [9]). Thus all the logspace counting classes are contained in DET .

In Sections 2 and 4 we prove some useful closure properties of #L, which have consequences on certain relationships between logspace counting classes. These properties are analogous to similar properties of #P, but not all of the proofs carry over to #L, since nondeterministic logspace machines are not able to record their own computation history.

∗A preliminary version was presented at the STACS conference held in Hamburg, Feb. 1991

†Institut für Informatik, Universität Würzburg, D-8700 Würzburg, Germany

‡Fachbereich Informatik, Humboldt-Universität Berlin, D-1086 Berlin, Germany

We therefore introduce new techniques that allow us to prove an analogous normal form theorem for MOD_{k}L-classes that was proved in [4] for MOD_{k}P-classes.

The importance of the MOD_{k}L-classes becomes obvious if one considers the computational power comprised in these classes. In Section 3 we prove that all standard problems of linear algebra over the finite ring Z/kZ are (logspace) complete for MOD_{k}L.

The notion of unambiguity is of great importance for nondeterministic computations. Valiant [18] used the term unambiguous computation for the definition of UP, the class of languages recognizable by polynomial time nondeterministic machines which never accept on more than one path. Today this type of machines is usually called unique. The power of space bounded unique computations was investigated in [8]. A different type of unambiguous computations refers to the number of computation paths leading to accepting configurations. If for each accepting configuration there is at most one path, we call the machine weakly unambiguous. (Note that this definition differs from the definition of (weakly) unambiguous machines in [13]). In the case of polynomial time it is no restriction if strong unambiguity^{1} is required, because every NP-machine can be simulated in a strongly unambiguous manner. On the other hand no such simulation is known for space bounded computations. In the case of logarithmic space bound the restriction to weakly unambiguous machines leads to a possibly proper subclass of NL that contains UL, the logspace analogon of UP. Weakly unambiguous computations on logarithmic space cannot have more than polynomially many accepting paths. The property of having only polynomially many accepting paths results in the case of polynomial time in the class FewP^{2} [1], [20]. An analogous definition of FewL is possible, but it doesn’t lead to analogous results. In Section 4 we therefore introduce the class LogFewNL of languages recognizable by logarithmic space bounded weakly unambiguous machines as adequate logspace version of FewP. The generalized class Few [20] accordingly leads to a new class LogFew. We then show that LogFew is contained in MOD_{k}L for all k, and an analogous result holds for LogFewNL.

2 Closure properties of #L and MOD_{k}L-Classes

In this section we define the class #L as an analogon of Valiant’s class #P [19], and we prove the closure of #L under addition, multiplication and binomial coefficient with constants. Then we introduce logspace-MOD-classes and use the closure properties of #L to show a normal form theorem for these classes. As a consequence of this normal form theorem, all logspace-MOD-classes are closed under union.

Definition 1 A function f belongs to #L, if there is a nondeterministic logspace Turing machine, such that for all inputs x, all computation paths terminate and the number of accepting computation paths is equal to f(x).

The following lemma gives some closure properties that hold for all functions in #L.

1In [13] machines are defined to be strongly unambiguous if for every pair of configurations there is at most one computation path leading from the first configuration to the second.

2Allender called this class FN P, Cai and Hemachandra called it FewN P.

Lemma 2

(i) #L is closed under addition and multiplication,

(ii) If f ∈ #L and k ≥ 0 is a constant, then g ∈ #L, where g(x) := \binom{f(x)}{k}.

(By \binom{a}{b} we denote the binomial coefficient.)

Proof:

(i) is clear.

(ii) Let M be a machine with f(x) accepting paths on input x. The start configuration c_{0} of M on input x can be written down in logarithmic space. We construct a machine M′ as follows:

On input x machine M′ writes the start configuration c_{0} of M on its tape, and a counter is initialized to 1. In general M′ will have several configurations of M written on its tape, and the counter will tell their number.

Now, in a loop, M′ cycles through all the configurations on the tape and each time nondeterministically chooses one of three possibilities:

a) replace the configuration by its first successor configuration

b) replace the configuration by its second successor configuration

c) replace the configuration by its first successor configuration and add the second successor configuration to the list of configurations on the tape and increment the counter by 1.

M′ rejects if the counter exceeds k, or if any of the configurations is rejecting, or if all configurations are accepting but the counter is less than k.

M′ accepts if all configurations are accepting and the counter is exactly k.

The space used by M′ is essentially the space needed for up to k configurations of M, and so it is still logarithmic in |x|, because k is a constant.

Note that this machine chooses k different paths of M and simulates them in parallel, i.e. this machine has exactly \binom{f(x)}{k} accepting paths, if k > 0. The case k = 0 is trivial, because we only need a machine with exactly one accepting path on every input.

The generalization of the second part of Lemma 2 to the case where k is not a constant is not possible with the proof technique that was used here. Therefore we will need a new method for this case, which we will develop in Section 4.

Many complexity classes based on logspace computations can be defined by posing conditions on the numbers of accepting (and/or rejecting) computation paths of a nondeterministic logspace machine. Examples are NL (as defined in the introduction), co − NL, and PL (cf. [6]). All these classes are subclasses of L^{#L}, the set of languages accepted by logspace Turing machines using an oracle from #L. We will use a weak type of function oracle for the precise definition of L^{#L}. For a function f ∈ #L let

bin(f) := {(x, i)| the i-th bit of f(x) is 1}.

Then L^{#L} is defined by:

L^{#L} := {A| A is logspace Turing-reducible to bin(f) for some f ∈ #L}.

Let DET denote the class of problems which are N C^{1}-reducible to the computation of integer determinants. Very recently Àlvarez and Jenner [2] proved that #L is contained in DET . This can be sharpened, thus giving a general upper bound for logspace counting classes:

Theorem 3 L^{#L} ⊆ DET .

Proof: (sketch)

We assume familiarity with the notion of truth-table-reductions. In [12] the equivalence of Turing-reductions and truth-table-reductions is proved for deterministic logspacebounded computations.

Let M be a deterministic logspace Turing machine that accepts language A using an oracle set B. Equivalently we can assume that there are two deterministic logspace Turing machines G_{M} and E_{M} which work as follows:

• Started on input x, machine G_{M} generates a list Query(M, x) of pairs (C_{i}, α_{i}), 0 ≤ i ≤ t(x), consisting of all possible oracle queries α_{i} that M can produce on input x (independently from the oracle) and the corresponding configurations of M (configuration C corresponds to a certain query, if in the computation tree of M on x, there is no QUERY-configuration between C and the actual QUERY-configuration, and C is either the start configuration or a YES- or NO-configuration (cf. [3])). For a set S let Answers(M, x, S) be the list Query(M, x) with the queries replaced by the correct oracle answers, i.e. each α_{i} is replaced by 1 if α_{i} ∈ S, or by 0 if α_{i} ∉ S.

• Started on a list Answers(M, x, S) of pairs (C_{i}, b_{i}), where the C_{i}’s are the configurations from the list above and the b_{i}’s are Boolean values, E_{M} interprets the b_{i}’s as oracle answers to the queries to which the C_{i}’s correspond, and accepts if M would accept receiving these answers. Especially, E_{M} accepts Answers(M, x, B) if and only if x ∈ A.

Now let A be accepted by the deterministic logspace Turing machine M with oracle bin(f) and f ∈ #L. Since #L ⊆ DET , the assignment

Query(M, x) ⟶ Answers(M, x, bin(f))

can be computed in DET . On the other hand, logspace computations can be simulated in DET ([9]). Hence, the work of G_{M} and of E_{M} can be done within DET , thus A ∈ DET .

Remark: In [9] DET is referred to as a class of functions rather than a class of languages. A standard binary encoding (as already mentioned for #L-functions) translates between these two points of view. Therefore we will not stress the distinction between function and language classes.

The following classes are defined via functions from #L:

Definition 4 Let k ≥ 2 be an integer. MOD_{k}L is the class of sets A, such that there is an f ∈ #L with

x ∈ A ⟺ f(x) ≢ 0 mod k.

If k is a prime number, then MOD_{k}L satisfies a number of closure properties:

Lemma 5 Let k be a prime number.

(i) MOD_{k}L is closed under intersection, union, and complement.

(ii) MOD_{k}L is closed under logspace disjunctive reducibility.

(iii) MOD_{k}L is closed under logspace conjunctive reducibility.

(iv) MOD_{k}L is closed under join.

Proof: The proofs are identical to those for MOD_{k}P (Lemma 26, (i) - (iv) in [7]).

Since the normal form theorem proved in [7] for MOD_{k}P-classes depends merely on the closure properties of Lemma 2 and Lemma 5 we obtain a normal form theorem for the MOD_{k}L-classes in exactly the same manner.

Theorem 6 Let k = p_{1}^{e_{1}} · p_{2}^{e_{2}} · . . . · p_{m}^{e_{m}} be the prime factorization of k ≥ 2. Then A ∈ MOD_{k}L if and only if there are sets B_{i} ∈ MOD_{p_{i}}L (1 ≤ i ≤ m) with A = ⋃_{i=1}^{m} B_{i}. Especially, the classes MOD_{k}L and MOD_{p_{1}·p_{2}···p_{m}}L are equal.

Corollary 7 For all k ≥ 2 the class MOD_{k}L is closed under union.

3 Importance of Logspace-MOD-Classes

We now give a characterization of the classes MOD_{k}L by complete problems. The notion of reducibility onto which our considerations are based is logspace reducibility. Recall, a language A is said to be logspace (many one) reducible to a language B (A ≤_{m}^{log} B) if there is a function f : {0, 1}^{∗} ⟶ {0, 1}^{∗} such that

(i) for all words w: w ∈ A ⟺ f(w) ∈ B

(ii) there is a Turing machine which started on an arbitrary input w stops with the word f(w) on a special output tape using no more than log(|w|) cells on the work tapes during the computation.

One can prove with standard arguments that MOD_{k}L is closed against logspace reductions.

A language A is said to be complete for MOD_{k}L if A ∈ MOD_{k}L and for all B ∈ MOD_{k}L holds B ≤_{m}^{log} A. The language MOD_{k}-GAP is easily seen to be complete for MOD_{k}L, where

MOD_{k}-GAP := {w | w is a directed acyclic graph on the vertex set {1,…, n}, whose number of paths from vertex 1 to vertex n is not divisible by k }

(A proof for the case k = 2 can be found in [14]. The generalization is straightforward.)

Now, using an idea of Cook [9], we reduce MOD_{k}-GAP to NONSINGULAR_{k}, the set of all quadratic non-singular matrices over the ring Z/kZ.

NONSINGULAR_{k} := {w | w = w_{11}w_{12} … w_{1n}w_{21}w_{22} … w_{nn}, and (w_{ij}) is a non-singular matrix over Z/kZ }

(To ease notation we allow Z/kZ together with some special characters as input alphabet. This causes no difficulties since binary coding and decoding can be performed within constant space as long as k is fixed.)

Proposition 8 NONSINGULAR_{k} is complete for MOD_{k}L.

Proof: To show MOD_{k}-GAP ≤_{m}^{log} NONSINGULAR_{k} let A be the adjacency matrix of a directed acyclic graph G on the vertex set {1,…, n}. Obviously, A is an upper triangular with zero diagonal. Therefore we have A^{n} = (0). Let M = I − A. Then M^{−1} = I + A + A^{2} + … + A^{n−1}. Observe that the (i, j)-th entry of A^{k} equals the number of paths of length k in G from i to j. Hence the number of paths from 1 to n equals the (1, n)-th entry of M^{−1}. On the other hand, since det(M) = 1 this entry equals the absolute value of the determinant of the matrix (I − A|(n, 1)) obtained from I − A by deletion of the n-th row and 1st column. Hence the number of interest is not divisible by k if and only if (I − A|(n, 1)) is non-singular over Z/kZ.

To show NONSINGULAR_{k} ∈ MOD_{k}L we use a construction of Berkowitz [5] which shows that the computation of determinants over a certain ring is N C^{1}-reducible to the computation of an iterated product of matrices over the same ring. (Refer to [9] for a definition of N C^{1}-reducibility.) To be more precise we give a language definition of the problem:

ITMATPROD_{k} :=

{(A(1), A(2),…, A(n), bin(i), bin(j), r) | A(1),…, A(n) are n × n matrices over Z/kZ, such that the (i, j)-th entry of A(1) · A(2) ·. . . · A(n) ≢ r mod k}

Since logspace reducibility is less restrictive than N C^{1}-reducibility we can use this construction. It remains to show that ITMATPROD_{k} can be computed within MOD_{k}L. We use the definition of a matrix product in a very direct way to construct a machine M having as number of accepting paths exactly the value of the (i, j)-entry of A(1)·. . .·A(n). First M writes [1, i, j] on its tape. Now M nondeterministically chooses a number z from the range 1,…, n, then M nondeterministically chooses a number w from the range 1,…, A(1)_{iz}, and replaces [1, i, j] on its tape by [2, z, j]. (If A(1)_{iz} = 0 then have M reject.)

Assume by induction that now on each computation path with [2, z, j] on the tape (z = 1,…, n) the machine will branch in such a way that the number of accepting paths will be the (z, j)-entry of A′ := A(2) ·. . . · A(n). Then M will have

∑_{z=1}^{n} ∑_{w=1}^{A(1)_{iz}} A′_{zj} = ∑_{z=1}^{n} A(1)_{iz} · A′_{zj} = (A(1) · A′)_{ij}

accepting paths as desired, and M as a MOD_{k}L-machine will accept if and only if that entry is not divisible by k.

The induction begins with [n, w, j] on the tape and the task to produce A(n)_{wj} accepting paths. That is easy.

By the normal form theorem (Theorem 6) it is reasonable to consider the classes MOD_{k}L for k prime seperately. Since in this case MOD_{k}L is closed under complement, the test whether the determinant of a certain matrix is congruent to zero (or to any other value) modulo k can be done in MOD_{k}L. In that sense computation of determinants over Z/kZ can be done in MOD_{k}L. Together with this problem many other problems of linear algebra belong to MOD_{k}L. We will list a few of them only by suggestive names in the following theorem, since a formalization as above would be easy but tedious.

Theorem 9 Let k be a prime number. The following problems from linear algebra over Z/kZ are complete for MOD_{k}L:

(i) inversion of matrices

(ii) powering of matrices

(iii) computation of the coefficients of characteristic polynomials

(iv) rank computations

(v) choice of a linearly independent subset of a given set of vectors

(vi) computing a basis of the kernel of a linear map given by a matrix

(vii) computing a solution of a linear system of equations.

Proof:

In [9] and [7] all these problems considered over the ring of integers have been shown to be equivalent w.r.t. N C^{1}-reductions. The proofs of the computational equivalence of (i)–(iii) with the computation of determinants on the one hand, and of (iv)–(vii) with each other on the other hand still work over Z/kZ. Using the theory of Jordan normal forms, Mulmuley proves in [15] that rank computation over some finite field R is (w.r.t. N C^{1}-reductions) as hard as computing the coefficients of the characteristic polynomial of a matrix over R[x]. By Berkowitz [5] the latter can be reduced to iterated matrix product over R[x]. Iterated matrix product over Z/kZ[x] can be done in MOD_{k}L. This follows from the fact that multiplication of polynomials from Z/kZ[x] can be simulated by multiplication of matrices over Z/kZ, which is easy to implement on MOD_{k}L-machines.

Thus, since Z/kZ is a field, problems (i) through (vii) are computationally equivalent w.r.t. N C^{1}-reductions and, hence, also w.r.t. logspace reductions.

Remark: In case k is a composite number, problems (i), (ii), and (iii) are complete for co-MOD_{k}L.

4 Weakly Unambiguous Turing Machines

The proof of Beigel et al. in [4] that Few ⊆ MOD_{k}P for all k makes use of the fact that #P is closed under binomial coefficient over functions bounded by a polynomial in the input length. Such a closure property for the logspace case cannot be obtained by a parallel simulation like the one in the proof of the second part of Lemma 2, because this would need at least polynomial space. So we have to perform a serial simulation of definitely different computation paths without being able to remember a computation path. This is possible if we use only machines where at least the restriction of the transition graph (on configurations) to paths from the initial configuration to accepting configurations is a tree, like in the example of Picture 4.1.

Figure 4.1

Hence in this case we have an accepting tree of the form that is shown in Picture 4.2.

Figure 4.2

We call machines with such a transition graph weakly unambiguous. For this type of machines we will be able to find the right number of different computation paths in Lemmas 11 and 12. We now state formally what we mean by weakly unambiguous:

Definition 10 A nondeterministic machine is called weakly unambiguous if for all accepting configurations c there is at most one computation path leading from the initial configuration (for input x) to c.

Lemma 11 Let M be a weakly unambiguous logspace machine with f(x) accepting computation paths on input x, and let g be a logspace computable function. Then

h ∈ #L, where h(x) := \binom{f(x)}{g(x)}

Proof:

Let M be a weakly unambiguous machine with f(x) accepting computations on input x. We have to design a machine M′ that tries to find exactly g(x) accepting paths of machine M on input x. We have to make sure that the constructed machine finds every g(x)-tuple of accepting paths exactly once. We design M′ as follows.

On input x first compute g(x). If g(x) is greater than the maximal number of accepting configurations, then M′ rejects. (Note that the number of accepting computations cannot be greater than the number of accepting configurations.) Otherwise M′ can write the value of g(x) on its tape. Now M′ cycles through all configurations of M. If the current configuration is an accepting one then M′ nondeterministically chooses either to ignore it or to check whether there is a computation path from the start configuration to this configuration. M′ counts how often it chose to check an accepting configuration, and M′ accepts if and only if it checked exactly g(x) times and all checks were successful.

It is easy to see that this machine has exactly \binom{f(x)}{g(x)} accepting paths on input x. Note, however, that we needed the fact that M was weakly unambiguous in the proof to make sure that M′ can check uniquely (without generating multiple paths) the reachability of a configuration. Remark. The preceding lemma is still true when we admit some kind of bounded ambiguity, i.e. there exists a constant k, such that for every accepting configuration there are at most k computation paths from the start configuration to that configuration. The same holds for the following lemma.

Lemma 12 Let M be a weakly unambiguous logspace machine with f(x) accepting computation paths on input x, and let k be a constant, k ≥ 2. Then

h ∈ #L, where h(x) := k^{f(x)} − 1

Proof: The proof is very similar to that of Lemma 11. Let again M be a weakly unambiguous machine with f(x) accepting paths on input x. Construct M′ as follows.

M′ cycles through all configurations of M on input x. If the current configuration is an accepting one, then M′ nondeterministically decides whether to check that configuration or not. If M′ chooses to check and the check is successful then M′ nondeterministically chooses a number m (where 1 ≤ m ≤ k − 1). M′ accepts if and only if there was at least one check on that computation path and all checks were successful.

It can be easily seen that the number of accepting paths of this machine equals

∑_{i=1}^{f(x)} \binom{f(x)}{i} · (k − 1)^{i} = ∑_{i=0}^{f(x)} \binom{f(x)}{i} · (k − 1)^{i} − 1 = k^{f(x)} − 1

Now we will define the classes MODZ_{k}L, which differ from MOD_{k}L by the restriction that the underlying machine is not allowed to accept on a number a of computation paths, where a > 0 and a ≡ 0 mod k:

Definition 13 Let k ≥ 2 be an integer. MODZ_{k}L is the class of sets A, such that there is an f ∈ #L with:

x ∈ A ⟹ f(x) ≢ 0 mod k
x ∉ A ⟹ f(x) = 0

Note that MODZ_{k}L ⊆ MOD_{k}L ∩ NL. The reverse inclusion is not known.

Now we define the class LogFewNL which we feel is the adequate logspace equivalent to the class FewP:

Definition 14 A set A is in LogFewNL, if there exists a weakly unambiguous logspace machine with f(x) accepting paths on input x, such that

x ∈ A ⟺ f(x) > 0

Theorem 15 LogFewNL ⊆ MODZ_{k}L for all k ≥ 2.

Proof: Let A ∈ LogFewNL and M a machine with f(x) accepting paths on input x, such that x ∈ A ⟺ f(x) > 0. By Lemma 12 there is a logspace machine M′ with k^{f(x)} − 1 accepting paths on input x, and this is not divisible by k if f(x) > 0, but zero if f(x) = 0. Thus A is in MODZ_{k}L via machine M′.

Definition 16 A set A is in LogFew, if there exists a weakly unambiguous logspace machine with f(x) accepting paths on input x, and a logspace computable predicate R such that

x ∈ A ⟺ R(x, f(x))

Theorem 17 LogFew ⊆ MOD_{k}L for all k ≥ 2.

Proof: It is clear that for all a, b ≥ 2 : MOD_{a}L ⊆ MOD_{ab}L. Thus we need only show that LogFew ⊆ MOD_{k}L for prime numbers k ≥ 2.

Now let A be in LogFew via machine M, and let M have f(x) accepting paths on input x. Define

A′ := \{(i, x) |\binom{f(x)}{i} ≢ 0 mod k\}

Certainly A′ ∈ MOD_{k}L by Lemma 11. Now define

A′′ := {(i, x) ∈ A′ | ∀j > i : (j, x) ∉ A′}

Also A′′ ∈ MOD_{k}L, because f(x) is polynomially bounded, say f(x) ≤ p(|x|) for polynomial p, and we need only check if

(i, x) ∈ A′ (1) (i + 1, x),…, (p(|x|), x) ∉ A′ (2)

which is possible because of the closure of MOD_{k}L under complement, join, and logspace conjunctive reducibility.

Now on input x do the following:

Construct the series (i_{1}, x), (i_{2}, x),…, (i_{r}, x) with i_{1} < i_{2} < … < i_{r} ≤ p(|x|) and the property that

i = i_{j} for some j ⟺ i ≤ p(|x|) and R(x, i)

One can easily check that

x ∈ A ⟺ (i_{j}, x) ∈ A′′ for some j

and so A ∈ MOD_{k}L, because MOD_{k}L is closed under logspace disjunctive reducibility.

5 Concluding Remarks

We investigated closure properties of the logspace counting class #L, and it turned out that although the properties themselves are rather similar to the polynomial time case, the techniques needed to prove them are more complicated. We view this as another hint, that the behavior of logarithmic space machines is not comparable to polynomial time machines. The results are summarized in picture 5.1.

As naturally the various MOD_{k}L-classes and their relations could not be drawn completely here, we added only three of them as examples (let p be any odd prime). It should be clear how to generalize this picture to other MOD_{k}L and MODZ_{k}L-classes.

Moreover we gave a series of very natural problems from Linear Algebra that are complete in logspace-MOD-classes, thus pointing out the relevance of counting accepting computation paths of logspace machines.

A different type of counting, namely the so called Inductive Counting of Immerman [11] and Szelepcsényi [16] does not refer to the number of accepting paths, but to the number of reachable configurations. We want to emphasize here that this type of counting does not help solving questions like: Is ⊕L contained in NL?

In general the relationship between NL and the logspace-MOD-classes remains an open question. Moreover, it is still open, whether MOD_{k}L is closed under complement, even if k is not prime.

Figure 5.1

6 Acknowledgements

We thank Hans-Jörg Burtschick and Klaus-Jörn Lange for fruitful discussions about the subjects of this paper. Thanks are also due to Birgit Jenner, who helped us to considerably simplify our original proof of Lemma 11 and Lemma 12. We further thank Jacobo Torán and the unknown referees of the STACS 1991 conference for some helpful hints on a preliminary version.

References

[1] Eric W. Allender. The complexity of sparse sets in P. In Proc. of 1st Structure in Complexity Conf., number 223 in LNCS, pages 1–11. Springer, 1986.

[2] Carme Àlvarez and Birgit Jenner. A very hard log space counting class. In Proc. of 5th Conference on Structure in Complexity Theory, pages 154–168, 1990.

[3] José L. Balcácar, Josep Díaz, and Joaquim Gabarró. Structural Complexity Theory I. Springer, 1988.

[4] Richard Beigel, John Gill, and Ulrich Hertrampf. Counting classes: Threshold, parity, mods, and fewness. In Proc. of 7th STACS, number 415 in LNCS, pages 49–57. Springer, 1990.

[5] S.J. Berkowitz. On computing the determinant in small parallel time using a small number of processors. Inform. Proc. Letters, 18:147–150, 1984.

[6] Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559–578, 1989.

[7] Allan Borodin, J. von zur Gathen, and John E. Hopcroft. Fast parallel matrix and gcd computations. INFCON, 52:241–256, 1982.

[8] Gerhard Buntrock, Lane A. Hemachandra, and Dirk Siefkes. Using inductive counting to simulate nondeterministic computation. In Proc. of 15th MFCS, number 452 in LNCS, pages 187–194. Springer, 1990. (to appear in Information and Computation).

[9] Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Inform. and Control, 64:2–22, 1985.

[10] Thomas Gundermann, Nasser Ali Nasser, and Gerd Wechsung. A survey on counting classes. In Proc. of 5th Conference on Structure in Complexity Theory, pages 140– 153, 1990.

[11] Neil Immerman. Nondeterministic space is closed under complement. SIAM Journal on Computing, 17(5):935–938, 1988.

[12] Richard E. Ladner and Nancy A. Lynch. Relativization of questions about log space computability. Math. Systems Theory, 10:19–32, 1976.

[13] Klaus-Jörn Lange and Peter Rossmanith. Characterizing unambiguous augmented pushdown automata by circuits. In Proc. of 15th MFCS, number 452 in LNCS, pages 399–406. Springer, 1990.

[14] Christoph Meinel. Modified Branching Programs and Their Computational Power. LNCS. Springer, 1989.

[15] Ketan Mulmuley. A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. In Proc. of 18th STOC, pages 338–339, 1986.

[16] Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Informatica, 26:279–284, 1988.

[17] Jacobo Toran. Counting the number of solutions. In Proc. of 15th MFCS, number 452 in LNCS, pages 121–134. Springer, 1990.

[18] Leslie G. Valiant. The relative complexity of checking and evaluating. Inform. Proc. Letters, 5:20–23, 1976.

[19] Leslie G. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189–201, 1979.

[20] Jin yi Cai and Lane A. Hemachandra. On the power of parity polynomial time. In Proc. of 6th STACS, number 349 in LNCS, pages 229–239. Springer, 1989.

List of Symbols:

\binom{a}{b}
\binom{f(x)}{g(x)}
\binom{f(x)}{i}
\binom{f(x)}{k}

≥ ≤ ⊆ ≡ ≢ ⟺ ⟹

∑_{i=0}^{f(x)}

∑_{i=1}^{f(x)}

∑_{z=1}^{n}

∑_{z=1}^{n} ∑_{w=1}^{A(1)_{iz}}

DET FewL FewN P FewP #L ⊕L L^{#L} LogFewNL MOD MOD_{a}L MOD_{ab}L MOD_{k}L MOD_{p_{1}·p_{2}···p_{m}}L MOD_{p_{i}}L MOD_{k}P

MODZ_{k}L

MODZ_{k}P

N C^{1}
N C^{2}

NL

NP

#P

P

PL

PSPACE

UL

UP

Z/kZ