Complexity Classes with Finite Acceptance Types^{⋆}

Ulrich Hertrampf

Theoretische Informatik, Universität Würzburg, Am Exerzierplatz 3, D-97072 Würzburg, Germany

Abstract. Complexity classes with finite acceptance types are those classes that can be obtained by nondeterministic machines, if the global acceptance condition is of the form: the number of accepting computation paths is in the set A, for some fixed finite set A. We study the relationships between such classes, exhibiting conditions, under which one class is contained in another one relative to all oracles, or conversely there is an oracle seperation. The proof technique uses a key lemma which transforms the inclusionship question for these classes into an existence question for certain hypergraphs.

1 Introduction

Recently, a lot of characterization results for many complextiy classes in the area between P and PSPACE have been obtained, using nondeterministic polynomial time Turing machines with some kind of global acceptance condition. A very general framework, allowing characterizations of nearly all introduced complexity classes in this area, has been developed by Bovet, Crescenzi, and Silvestri in [1, 2].

In [5] (see also [6]) a polynomial time machine scheme for such characterizations is introduced using a finite set of k-valued functions, the so called locally definable acceptance types. A special case of finite acceptance types appears, if we just add up the number of accepting paths, but mapping all numbers greater than k to k. Filtering out those cases where this number is in subset A of {1, …, k} results in counting classes of finite acceptance type. These classes were introduced by Gundermann, and Wechsung [3], see also [4].

In [3, 4] the inclusionship structure of such classes was investigated for cases where the used sets A consisted of intervals. In the current paper we are interested in the general case, where A may be any finite set of natural numbers. We give a translation of the question, whether a given class is contained in another one, to the question, whether a certain sequence of hypergraphs (or set systems)

⋆ This research was supported by Deutsche Forschungsgemeinschaft, Grant number Wa 847/1-1, “k-wertige Schaltkreise”. Part of this work was done while the author was an assistant at Universität Trier.

exists, or not. Using this translation, we prove and disprove the existence of oracle separations in a wide variety of cases.

The organization of the paper is as follows: In Section 2 we give the formal definition of a complexity class with finite acceptance type, and we recall the connection between this kind of complexity and the concept of leaf languages from [1, 2] (see also [7]). Section 3 introduces hypergraph sequences. We prove some easy facts on existence or non-existence of special types of such sequences. Section 4 connects the existence question for hypergraph sequences with the inclusionship question for certain counting classes. Finally, in Section 5, the results of the previous sections are applied to obtain a nearly complete solution of the question, whether two given classes {a, b}P and {c, d}P can be separated by an oracle.

2 Counting Classes and Leaf Languages

We now give the formal definition of a finite acceptance class and a co-finite acceptance class, resp. These classes are counting classes in a strong sense, since the acceptance condition merely depends on the number of accepting computations, and no computation is done except that we stop counting after reaching a certain maximal value. By acc_{M}(x) we denote the number of accepting paths of machine M on input x.

Definition 1. A finite acceptance class C is a class of sets such that there exists a fixed finite set A ⊂ IN with the following property:

L ∈ C ⟺ ∃M (NTM) with x ∈ L ↔ acc_{M}(x) ∈ A. (⋆)

The finite acceptance class associated with set A is denoted by (A)P.

A co-finite acceptance class C is a class of sets such that the class D := co − C = {L | Σ^{∗} − L ∈ C} is a finite acceptance class.

Clearly a class C is a co-finite acceptance class if and only if there is a fixed co-finite set A ⊂ IN with property (⋆).

One can easily see that coNP is a finite acceptance class: take A to be {0}. Consequently, NP is the co-finite acceptance class co-(A)P. The class 1-NP is the finite acceptance class for A = {1} (this class is sometimes also called US).

All (co-) finite acceptance classes are contained in the Boolean Hierarchy:

Proposition 2. Let A ⊂ IN be a finite set, |A| = k. Then (A)P ⊆ NP(2k).

Proof. Let A = {a_{1}, a_{2}, …, a_{k}}. Let L ∈ A, and let M be a fixed machine such that x ∈ L ↔ acc_{M}(x) ∈ A. Define L^{≤c} := {x | acc_{M}(x) ≤ c} and L^{≥c} := {x | acc_{M}(x) ≥ c}. Obiously all sets L^{≤c} belong to coNP, all sets L^{≥c} belong to NP, and

L = (L^{≤a_{1}} ∩ L^{≥a_{1}}) ∪ … ∪ (L^{≤a_{k}} ∩ L^{≥a_{k}}).

Thus, by definition of the classes in the Boolean Hierarchy, L ∈ NP(2k).

Corollary 3. All classes of the types (A)P or co-(A)P are subclasses of BH, the union of all classes of the Boolean Hierarchy.

Complexity classes with finite acceptance types can also be characterized by their leaf languages. This depends on the fact that these classes can be described via nondeterministic polynomial time machines by a regular language in the following way:

– With every class C = (A)P, where A = {a_{1}, …, a_{k}}, the regular language

R_{A} = (0^{∗}10^{∗})^{a_{1}} ∪ … ∪ (0^{∗}10^{∗})^{a_{k}}

is associated.

– For every L ∈ C there is a polynomial time NTM M, such that on inputs from L, M’s computation in its leaves, read from left to right yields a word from R_{A}, and on inputs from \overline{L} a word from \overline{R_{A}}.

The leaf languages can be used to obtain oracle separations between two finite acceptance classes, or to prove the non-existence of such separations. This connection was given in [1, 2]. We need the following definition:

Definition 4. A language A is plt-reducible to B, A ≤_{m}^{plt} B, if there exist two functions f and g, each computable in polylogarithmic time on a deterministic machine with random access to the input, f is zero-one-valued, such that

x ∈ A ⟺ f(x, 1)f(x, 2) … f(x, g(x)) ∈ B.

It follows from the work of [1, 2] that plt-reduction is the key to proving existence or non-existence of oracle separations between two finite acceptance classes. We restate their result as follows:

Theorem 5 (Bovet, Crescenzi, Silvestri). Let C_{1} and C_{2} be two complexity classes with leaf languages A_{1} and A_{2}, resp. Then A_{1} is plt-reducible to A_{2} if and only if C_{1} is contained in C_{2} in all relativizations.

This allows us in the subsequent sections, to only consider leaf languages, when we talk about oracle separations.

3 Hypergraphs, Sequences, and Uniformity

In this section we will introduce our notion of hypergraphs, which are also called set systems in the literature. Various definitions are possible, e.g. sometimes the empty set is not allowed as a hyperedge, or each set is only allowed to occur at most once. We choose the most general definition.

Definition 6. A hypergraph H on the finite set X is a mapping H : 2^{X} ⟶ IN. The elements of X are called vertices of H. If for some Y ⊆ X the value H(Y) is greater than zero, then we call Y a hyperedge of multiplicity H(Y).

Obviously, the structure of a hypergraph does not depend on the set X, but in fact only on the cardinality of X. So we will always assume X to be the set {x_{1}, x_{2}, …, x_{n}}, when the cardinality of X is n.

In this paper we are mainly interested in sequences of hypergraphs:

Definition 7. A hypergraph sequence, also called H-sequence, is an infinite sequence of hypergraphs H_{1}, H_{2}, …, such that for all i ∈ IN, H_{i} is a hypergraph on {x_{1}, …, x_{i}}.

The hypergraph sequence H_{1}, H_{2}, … is a uniform H-sequence, if there exists a deterministic polynomial time algorithm, which on input (n, j_{1}, …, j_{k}) with j_{ν} ≤ n, (1 ≤ ν ≤ k), can compute H_{n}({x_{j_{1}}, …, x_{j_{k}}}).

The crucial property of (uniform) H-sequences, needed for the separations and inclusions in Section 5, is a correspondence between two sets of natural numbers:

Definition 8. We say that the H-sequence (H_{i})_{i∈IN} realizes the correspondence (A, B), where A, B ⊂ IN are finite sets, if for all i with i > max(A), we have

∑_{C′⊆C} H_{i}(C′) ∈ B ⟺ |C| ∈ A.

To understand the motivation for this definition, imagine a bitwise reduction, where every bit of the output merely depends on a fixed set of bits in the input, and it is set to 1 if and only if all these bits in the input are set to 1. Now we can, for each set of inputs, determine how many of the output bits depend exactly on that set. This number is H applied to the set of inputs. But if these input bits are all set to 1, then also all the output bits depending on proper subsets of this set of inputs, will be set to 1. So the number of outputs set to 1 for a given set of 1’s in the input can be computed by a sum like the one in the above definition. We will return to this point in Section 4.

Now we derive some easy correspondences that can be realized by uniform H-sequences.

Lemma 9. Let A = {a_{1}, …, a_{k}}, where a_{1} < a_{2} < … < a_{k}. Then the correspondence (A, {a_{1}, …, a_{k−1}, a_{k}+1}) is realized by a suitable uniform H-sequence.

Proof. Let for all i, H_{i}(Y) = 1, if |Y | ∈ {1, a_{k}}, and H_{i}(Y) = 0, in all other cases. Obviously this H-sequence is uniform, and it realizes the desired correspondence, since in sets with less than a_{k} elements, the only hyperedges are the ones with one element, but in sets with exactly a_{k} elements one additional hyperedge exists, consisting of all the a_{k} elements.

Lemma 10. Let A = {a_{1}, …, a_{k}}, where a_{1} < a_{2} < … < a_{k}. Then the correspondence (A, {a_{1} + 1, …, a_{k} + 1}) is realized by a suitable uniform H-sequence.

Proof. Let for all i, H_{i}(Y) = 1, if |Y | ∈ {0, 1}, and H_{i}(Y) = 0, in all other cases. Obviously this H-sequence is uniform, and it realizes the desired correspondence, since in every set there is the hyperedge consisting of the empty set, plus as many one-element hyperedges as there are elements.

Lemma 11. Let A = \{a, b\} with a < b, and let B = \{1, \binom{b}{a}\}. Then there is a uniform H-sequence that realizes the correspondence (A, B).

Proof. Let for all i, H_{i}(Y) = 1, if |Y | = a, and H_{i}(Y) = 0, otherwise. This uniform H-sequence has the desired property.

We also need some non-existence results. To make them as general as possible, we will consider all (possibly non-uniform) H-sequences here.

Lemma 12. Let A = {a, b} with a < b, and let B = {c, d} with c < d. If d − c < a − b, then there is no H-sequence that realizes the correspondence (A, B).

Proof. We assume that there is an H-sequence (H_{i})_{i∈IN} that realizes the correspondence (A, B). Define β_{i}(C) to be the sum ∑_{C′⊆C} H_{i}(C′). Define further X_{j,k} = {x_{j}, …, x_{k}} for all pairs (j, k) such that j < k. From the definition of A and B, it is clear that

β_{i}(X_{1,a}) ∈ {c, d} and β_{i}(X_{2,a+1}) ∈ {c, d}

but since β_{i}(X_{2,a}) ∉ {c, d}, then β_{i}(X_{1,a}), as well as β_{i}(X_{2,a+1}) have to differ from β_{i}(X_{2,a}). Consequently in the set X_{1,a} there is a hyperedge involving vertex x_{1}, and in set X_{2,a+1} there is a hyperedge involving vertex x_{a+1}, so

β_{i}(X_{1,a+1}) > max(β_{i}(X_{1,a}), β_{i}(X_{2,a+1}))

and from b ≥ a + 1 we conclude

β_{i}(X_{1,b}) > max(β_{i}(X_{1,a}), β_{i}(X_{2,a+1})).

Thus β_{i}(X_{1,a}) = c and β_{i}(X_{1,b}) = d, and the same argument yields β_{i}(C) = c, whenever |C| = a and β_{i}(C) = d, whenever |C| = b.

Now we can start with X_{1,a}, which yields value c, and successively add x_{a+1}, x_{a+2}, …, x_{b}. In every step, a simple argument as the one above shows, that the β_{i}-value has to increase at least by one, since an a-element subset of the new set always contains a hyperedge involving the newly added vertex. So after the b − a addition steps, we arrive at a value that is at least c + b − a > d. That is a contradiction, since by assumption β_{i}({x_{1}, …, x_{b}}) ∈ {c, d}.

Lemma 13. Let A = {a, b} with a < b, and let B = {1, d} with d > 1. If d < \binom{b}{a}, then there is no H-sequence that realizes the correspondence (A, B).

Proof. We assume that there is an H-sequence (H_{i})_{i∈IN} that realizes the correspondence (A, B). Define β_{i}(C) and X_{j,k} = {x_{j}, …, x_{k}} as above. We can derive as above that all a-element subsets C fulfill β_{i}(C) = 1, and all (a − 1)-element subsets C fulfill β_{i}(C) = 0. This means, that for a-element subsets C, we have H_{i}(C) = 1, and thus for b-element subsets C, β_{i}(C) ≥ \binom{b}{a}, because these sets contain \binom{b}{a} subsets of cardinality a, and all of these add a one to the sum for C. This contradicts the assumption.

Similar arguments show the following lemma:

Lemma 14. Let |A| > |B|, and 0 ∉ A. Then there is no H-sequence that realizes the correspondence (A, B).

4 The Main Lemma

In this section we want to link the concept of hypergraphs to the plt-reductions of Section 2. Recall that a plt-reduction in Section 2 was defined as a pair of functions f and g, and the result was the string f(x, 0)f(x, 1) … f(x, g(x)). This latter string we will refer to as h(x), thus viewing the reduction as a function h that takes a string x as argument and outputs another string h(x). To make things easier we will talk of h as the plt-reduction.

We start with two technical lemmas. For strings w ∈ {0, 1}^{∗}, we denote the number of 1-bits in w by |w|_{1}.

Lemma 15. Let h be a plt-reduction, reducing L_{1} to L_{2} (L_{1}, L_{2} ⊆ {0, 1}^{∗}). Let m and k be such that |x|_{1} ≤ m ⇒ |h(x)|_{1} ≤ k. Then there exists a plt-reduction h′ such that

|x|_{1} ≤ m ⇒ |h′(x)|_{1} = |h(x)|_{1}

and

|x|_{1} > m ⇒ k < |h′(x)|_{1} ≤ \binom{|x|_{1}}{m}k + \binom{|x|_{1}}{m + 1}(k + 1)

(Note that the new reduction does not necessarily reduce L_{1} to L_{2} anymore, but on inputs with at most m 1-bits, it still behaves like h.)

Proof. Let h(x) = f(x, 1)f(x, 2) … f(x, g(x)). So if |x|_{1} ≤ m then at most k of the bits f(x, j) have value one. Define g′ as follows:

g′(x) = g(x) + \binom{|x|}{m + 1}(k + 1)

We understand each of the values g(x) + 1, g(x) + 2, …, g′(x) as an encoding of an (m + 1)-tuple of bits from x, each (m + 1)-tuple occuring exactly k + 1 times.

Now we can define f′:

f′(x, j) = \{ \begin{matrix}1, & if j ≤ g(x) and f(x, j) = 1 and the computation \\ & of f on input (x, j) reads at most m ones of x \\ & or j > g(x) and the (m + 1)-tuple of bits in x encoded \\ & by j consists entirely of bits of value one \\ 0, & otherwise \end{matrix}

We abbreviate the plt-reduction defined by f′ and g′ as h′(x).

If |x|_{1} ≤ m then f′(x, j) has value one, if and only if j ≤ g(x) and f(x, j) = 1, thus |h′(x)|_{1} = |h(x)|_{1} in this case, as desired.

Now let |x|_{1} > m. We have exactly \binom{|x|_{1}}{m+1} different (m + 1)-tuples that will cause bits of value one, each (k + 1) times. So the number of one bits produced by f′(x, j) for j > g(x) is exactly \binom{|x|_{1}}{m+1}(k + 1), and especially this value is greater than k. It remains to show that no more than \binom{|x|_{1}}{m}k values of j with j ≤ g(x) result in f′(x, j) = 1: When f′(x, j) has value one for such a j, then f must read at most m ones of x. This means that there is a word x′ with at most m ones such that also f(x′, j) = 1. Consequently, there exist at most k such values of j for any possible x′. Since the number of words x′ with this property is bounded by \binom{|x|_{1}}{m} and each x′ can cause only k ones in h(x) and thus also in h′(x), we have the bound of \binom{|x|_{1}}{m}k for the number of ones among the f′(x, j) with j ≤ g(x). This completes the proof.

Lemma 16. Let h be a plt-reduction with |x|_{1} ≤ m ⇒ |h(x)|_{1} ≤ k. Then for sufficiently large x there is a set of indices I ⊆ {1, …, |x|}, such that

1. |I| = m

2. ∀J ⊆ I : U(X_{J}) ∩ I ⊆ J

3. J_{1} ⊆ J_{2} ⊆ I ⇒ U(X_{J_{1}}) ⊆ U(X_{J_{2}})

Here, X_{J} = z_{1}z_{2} … z_{n} with z_{i} = 1 ⇔ i ∈ J, and U(x) is the set of all indices j, such that there is a computation in h(x) that outputs 1 and reads the j-th input bit.

Proof. We first prove the existence of a set I of cardinality m fulfilling condition 2:

There are \binom{n}{m} different sets I, which is Θ(n^{m}). How many of these sets violate condition 2 because of a subset J of fixed cardinality j (0 ≤ j ≤ m)? Let J be fixed. Then

|X_{J}|_{1} = j ≤ m ⇒ |h(X_{J})|_{1} ≤ k ⇒ |U(X_{J})| ≤ k · log^{c} n

for some constant c. So to violate condition 2 I has to include at least one of the k · log^{c} n elements of |U(X_{J})| which is not in J.

Now we have only O(n^{j}) choices for J, and only O(n^{m−j−1} log^{c} n) possible extensions of J to a set I contradicting condition 2. So there are only O(n^{m−1} log^{c} n) choices of I where 2 is violated with a set J of size j. Summing up over all values of j gives us still only O(n^{m−1} log^{c} n) bad choices for I, but there are Θ(n^{m}) choices for I altogether. Thus we can choose an I fulfilling condition 2.

As to condition 3, consider the plt-reduction on X_{J_{1}} and X_{J_{2}}. Every one bit in the image of X_{J_{1}} depends only on bits from J_{1} or from outside I, because of condition 2. But all bits in J_{1} and outside I are the same for X_{J_{1}} and X_{J_{2}}. So the one bits in the image of X_{J_{1}} are one bits in the image of X_{J_{2}} too. Consequently U(X_{J_{1}}) ⊆ U(X_{J_{2}}).

Now we are ready to prove our main lemma:

Lemma 17. Let A and B be two finite sets. If there exists a plt-reduction, reducing the leaf language of (A)P to the leaf language of (B)P, then there exists an H-sequence (H_{i})_{i∈IN} that realizes the correspondence (A, B).

Conversely, if a uniform H-sequence realizes the correspondence (A, B), then there is a plt-reduction, reducing the leaf language of (A)P to the leaf language of (B)P.

Proof. By Lemma 15 we can modify the plt-reduction in a way that it still reduces the leaf language of (A)P to the leaf language of (B)P, but for every number m we can give an explicit bound on the number of ones in images of inputs with m ones. So for every desired size we can apply Lemma 16 to get an input x with a set of indices I fulfilling the three conditions 1, 2, and 3. Thus these indices form a sort of monotonicity area:

When x is an input such that only bits with index from I can have value one, and if y is another input of that kind with x_{i} = 1 ⇒ y_{i} = 1, then also all one bits in the image of x remain one bits in the image of y. When the plt-reduction is h, we can formalize this by

x ≤ y ⇒ h(x) ≤ h(y)

where the ordering is meant bitwise.

We can exploit this by taking I as the basic set for a hypergraph H, and defining H(J) = the number of bits in h(X_{I}) that are ones already in h(X_{J}), but are zero in all h(X_{J′}), when J′ ⊂ J. Obviously β(J) = |h(X_{J})|_{1}. So for all J with |J| ∈ A we have β(J) = |h(X_{J})|_{1} ∈ B, since h maps all words x with |x|_{1} ∈ A to words h(x) with |h(x)|_{1} ∈ B by definition. Thus the sequence of hypergraphs defined that way realizes the correspondence (A, B).

For the second part, note that the following pair (f, g) reduces the leaf language of (A)P to the leaf language of (B)P:

g(x) = max(B) ∑_{a∈A} \binom{|x|}{a}

Let every j (1 ≤ j ≤ g(x)) be the encoding of a pair consisting of an a-tuple of indices in x and a number from 1 to max(B). We can encode each such pair exactly once in a value j. Now define f as follows:

f(x, j) = \{ \begin{matrix}1, & if j encodes the pair (i, d) and the hyperedge associated \\ & with i exists and has multiplicity at least d \\ 0, & else \end{matrix}

5 Application: Results about Inclusion Relations

In this section we are going to combine Lemma 17 with the results of Section 3 to obtain separations and inclusions between several types of complexity classes with finite acceptance types.

In the following, speaking of pairs (a, b) we generally assume a < b. The first result in this line is derived directly from Lemma 9 and Lemma 10:

Theorem 18. Let the pairs (a, b) and (c, d) be such that a ≤ c and b−a ≤ d−c. Then ({a, b})P ⊆ ({c, d})P in all relativizations.

Combining Lemma 11 with Theorem 18 we get:

Theorem 19. Let the pairs (a, b) and (c, d) be such that c ≥ 1 and d−c ≥ \binom{b}{a}−1. Then ({a, b})P ⊆ ({c, d})P in all relativizations.

On the other hand, we conclude from Lemma 12:

Theorem 20. Let the pairs (a, b) and (c, d) be such that b − a > d − c. Then there is an oracle, such that in the relativized world ({a, b})P ⊈ ({c, d})P.

Finally, from Lemma 13 we see:

Theorem 21. Let d < \binom{b}{a}. Then there is an oracle, such that in the relativized world we have ({a, b})P ⊈ ({1, d})P.

These results are summarized in the following picture, where in the columns we fix the value a, (a ≥ 0), and in the rows we have b, (b > a). For a given pair (a, b) the part in the upper right, looking like a “W” is known to include ({a, b})P, the parts on the left and on the bottom do not include ({a, b})P, (i.e. relative to an oracle), and for the finite part in the middle it is not known, which case applies.

[figure: ?; a=0; a=1; a=2; a=3; ⋮; b=1; b=2; b=3; b=4; b=5; ⋯; (a, b); (1, \binom{b}{a}); (c, d)P; ⇒ (a, b)P ⊈ (c, d)P (rel.); (c′, d′)P; ⇒ (a, b)P ⊆ (c′, d′)P; ⊆; ⊈; ⊈]

We proceed with a result about finite acceptance type classes, where the acceptance types have a different number of elements:

Theorem 22. Let |A| > |B|, and 0 ∉ A. Then there is an oracle, such that in the relativized world (A)P ⊈ (B)P.

Proof. This follows from Lemma 14.

A generalization of the technique used here also shows:

Theorem 23. Let A and B be two finite sets of natural numbers. Then there is an oracle, such that in the relativized world co-(A)P is not contained in (B)P, and there is an oracle such that in the relativized world (A)P is not contained in co-(B)P.

As a corollary of this result we obtain a well known fact:

Corollary 24. There is an oracle, separating NP from coNP.

Acknowledgement. I am grateful to Christoph Meinel for his support. Thanks are also due to Heribert Vollmer for fruitful discussions on the paper’s subject.

References

1. D. P. Bovet, P. Crescenzi, R. Silvestri, Complexity classes and sparse oracles; 6^{th} Structure in Complexity Theory Conference (1991), pp. 102–108.

2. D. P. Bovet, P. Crescenzi, R. Silvestri, A uniform approach to define complexity classes; Theoretical Computer Science 104 (1992), pp. 263–283.

3. T. Gundermann, G. Wechsung, Counting Classes of finite acceptance types; Computers and Artificial Intelligence 6 (1987), pp. 395–409.

4. T. Gundermann, N. A. Nasser, G. Wechsung, A survey on counting classes; 5^{th} Structure in Complexity Theory Conference (1990), pp. 140–153.

5. U. Hertrampf, Locally definable acceptance types for polynomial time machines; 9^{th} Symposium on Theoretical Aspects of Computer Science (1992), LNCS 577, pp. 199–207.

6. U. Hertrampf, Locally definable acceptance types – the three-valued case; 1^{st} Latin American Symposium on Theoretical Informatics (1992), LNCS 583, pp. 262– 271.

7. U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, K. W. Wagner, On the power of polynomial time bit-reductions; 8^{th} Structure in Complexity Theory Conference (1993), pp. 200–207.

This article was processed using the LaTEX macro package with LLNCS style