On the Power of Polynomial Time Bit-Reductions

Extended Abstract

Ulrich Hertrampf  Clemens Lautemann and Thomas Schwentick
Theoretische Informatik  Institut für Informatik
Universität Trier  Universität Mainz
D-5500 Trier, Germany  D-6500 Mainz, Germany

Heribert Vollmer and Klaus W. Wagner

Theoretische Informatik Universität Würzburg D-8700 Würzburg, Germany

Abstract

For a nondeterministic polynomial time Turing machine M and an input string x, the leaf string of M on x is the 0-1-sequence of leaf-values (0 ∼ reject, 1 ∼ accept) of the computation tree of M with input x. The set A is said to be bit-reducible to B if there exists an M as above such that for every input x, x is in A if and only if the leaf string of M on x is in B. A class C is definable via leaf language B, if C is the class of all languages that are bit-reducible to B. We are interested in the question how complex a leaf language must be in order to characterize some given class C. This question leads to the examination of the closure of different language classes under bit-reducibility. We settle this question for subclasses of regular languages, context free languages, and a number of time and space bounded classes. As consequences we get a number of surprising characterizations for PSPACE.

1 Introduction

The nondeterministic polynomial time Turing machine is one of the central computation models in structural complexity theory. A great number of complexity classes which evolved in the past can be defined with such machines. A possible way to do so is the following: Associate the output value 0 with a rejecting computation path and 1 with an accepting path of such a machine M on some input x and assume some ordering on the set of all paths; then there is a unique sequence w of outputs over all paths of the computation tree of M on x. We call w the leaf string of M on x. If for languages A and B there exists a nondeterministic polynomial time machine M such that x is in A if and only if the leaf string of M on x is in B, then A is bit-reducible to B.

Now classes can be defined by using specific leaf languages. Take as an example the class NP: A nondeterministic polynomial time Turing machine M defines an NP-language A, if some input x belongs to A if and only if the leaf string of M on x is a member of the regular language

{ w ∈ {0, 1}^{∗} | 1 appears at least once in w }.

As another example, the class ⊕ P is defined via the regular language

{ w ∈ {0, 1}^{∗} | the number of 1’s in w is odd }.

The definability of complexity classes with such leaf languages was examined by Bovet, Crescenzi, and Silvestri in [6, 7]. They were interested mainly in a unified framework suitable to define lots of well known complexity classes, because they wanted to give general conditions for the possibility of oracle separations between such classes.

In this paper we are interested in the following question: Given some bounds on the complexity of the leaf language; what complexity classes can be defined via leaf languages which fall under this bound? To state it in other terms: Given a class of languages, what is the closure of this class under bit-reducibility? E.g. consider the class PSPACE. It can be characterized via polynomial time alternating Turing machines. Given a leaf string of such a machine, a pushdown automaton can directly evaluate the string by simulating the polynomial depth AND/OR-circuit defined by the alternating machine on the input under consideration. The automaton needs a pushdown size polynomial in the length of the input of the alternating machine, i.e. logarithmic in the length of the leaf string. Therefore, PSPACE is characterized by leaf languages with logarithmic pushdown size complexity. But surprisingly, it turns out that PSPACE can be characterized via leaf languages of lower complexity; namely regular languages. PSPACE is equal to the class of languages which are bit-reducible to some regular language. This implies among others the following interesting consequences:

• PSPACE is the class of languages accepted by AC^{0}-uniform bounded width exponential size branching programs.

• PSPACE computations can be divided into an exponentially long series of “slices” of complexity AC^{0}, such that the number of bits transferred to the next slice is bounded by a constant. This slightly improves a result of Cai and Furst from [9], where it is shown, that PSPACE is LOGSPACE-serializable.

• PSPACE computations can be characterized by polynomial depth computation trees, where the leaves are associated with a constant value, and in inner nodes one associative function is evaluated, i.e. PSPACE is definable by an associative locally definable acceptance type in the sense of [14, 15].

We systematically study, which classes can be defined via leaf languages of different complexity. We start with regular languages and some subclasses of that class and determine their closure under bitreducibility. The proofs turn out to be more or less a translation of methods from [3, 4] from the context of NC^{1} into the context of polynomial space. This leads us to the question what the general preconditions for a possibility of such a translation are. For this aim, we do not only consider bit-reducibility as above (which we call from now on polynomial time bit-reducibility) but also a polylogarithmic time bit-reducibility, and we establish general translational results relating these two notions. We will prove a number of results of the form: If the set A is complete for some class under polylogarithmic time bit-reducibility, then A is complete for the class of exponentially higher complexity under polynomial time bit-reducibility. This will enable us finally to determine the closure of a large number of time- and space-bounded classes under (polynomial time) bit-reducibility.

Again, we get another interesting statement about the class PSPACE (implicit in [13, 8]): Auxiliary pushdown automata with polynomial space and exponential time bound can already be simulated by Turing machines operating in polynomial space.

After giving some relevant definitions in the next section, we present in Section 3 and 4 our results on the class PSPACE. Some hierarchies within PSPACE are examined in Section 5. It will turn out that they can be characterized with leaf languages taken from certain subclasses of the class of regular languages. Then, we introduce the notion of polylogarithmic time bit-reducibility and in Section 7, we present our translational method and use it there to give results on leaf languages taken from fairly general time bounded classes and in Section 8 to give results for reduction to classes bounded by other complexity measures. Finally in Section 9 we make some concluding remarks.

2 Notations and definitions

We assume the reader to be familiar with standard complexity theory notions. Our notation here is standard; see e.g. [1, 2, 16]. IN denotes the set of natural numbers. Pol denotes the set of all polynomials. FP denotes the class of all functions computable in deterministic polynomial time. The unary identity function is denoted by id. For a class C and k ∈ IN, we say that A ∈ Mod_{k} C if there exists some B ∈ C and some p ∈ Pol such that for all x, x ∈ A if and only if the cardinality of { y | |y| ≤ p(|x|)∧(x, y) ∈ B } is divisible by k [5]. Then MOD^{∗}P denotes the union of all classes which can be generated from the class P by finitely many applications of Mod_{k}-operators (k ∈ IN), and MOD-PH denotes the union of all classes which can be generated from the class P by finitely many applications of existential, universal and Mod_{k}-operators (k ∈ IN). CFL (DCFL, REG, resp.) denotes the class of context-free (deterministic context-free, regular, resp.) languages. By 2-auxPD-DSPACE-TIME(s, t) (2-auxPD-NSPACE-TIME(s, t)) we denote the class of languages which are accepted by deterministic (nondeterministic) 2-way auxiliary pushdown automata with workspace bound s and time bound t.

A branching program B [19] is a directed acyclic graph such that exactly one node is of indegree 0, and every node is either of outdegree 2 and labelled by a Boolean variable, or of outdegree 0 and labelled by a Boolean constant. Let n ∈ IN be maximal such that x_{n} appears somewhere as a label in B. Then B recognizes a subset of {0, 1}^{n}. The computation of such a program on some input w = w_{1}w_{2} ⋯ w_{n} starts at the node with indegree 0. If one reaches an outdegree 2 node labelled by x_{i}, one proceeds with the left successor if w_{i} = 0 and with the right successor if w_{i} = 1. If one reaches an outdegree 0 node the computation stops and the output is the label of that node. The size of a branching program B is the number of nodes of B (we will from now on identify B with {1, 2, …, |B|}); a level of B is a set of nodes of B with equal distance to the indegree 0 node; the width of B is the maximal cardinality of a level of B. Recognition of a subset of {0, 1}^{∗} is done by a family (B_{1}, B_{2}, …) of branching programs, one for each input length. Such a family is called AC^{0}-uniform if there is a family of polynomial size, constant depth circuits (which, in it’s turn, is DLOGTIME-uniform), which on input (1^{n}, k) produces the label and the successors of node k in B_{n}. A permutation branching program of width w and size ℓ [3] is a sequence of triples (i_{j}, σ_{j}, π_{j}) for 1 ≤ j ≤ ℓ, where σ_{j}, π_{j} ∈ S_{w} (the symmetric group on w elements). Given input w = w_{1}w_{2} ⋯ w_{n} such an instruction yields the result σ_{j}, if w_{i_{j}} = 0, and π_{j}, if w_{i_{j}} = 1. The result of the whole computation is the result of the multiplication of these single results. Set recognition via a family of permutation branching programs is defined similar to the above. A family of permutation branching programs is AC^{0}-uniform if there is a family of polynomial size, constant depth circuits (which, in it’s turn, is DLOGTIME-uniform), which on input (1^{n}, k) produces the k-th instruction of the n-th program.

For a reducibility notion ≤_{y}^{x} and a set B, let R_{y}^{x}(B) denote the set of all languages reducible to B via ≤_{y}^{x}, i.e. R_{y}^{x}(B) = { A | A ≤_{y}^{x} B }. If C is a class of sets, then R_{y}^{x}(C) = ⋃_{B∈C} R_{y}^{x}(B).

For a class C, let BC(C) denote the boolean closure of C.

In order to make precise our notion of defining a class via a leaf language, we need the following definition (which is similar in spirit to a definition from [7]).

2.1 Definition. Let A and B be two sets. Then A is polynomial time bit-reducible to B, in symbols A ≤_{m}^{p,bit} B, iff there exist functions f, g ∈ FP where f is zero-one-valued, such that

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

If M is a nondeterministic polynomial time Turing machine which is normalized in the sense that on input x every path of M has length exactly p(|x|) for some polynomial p, and if we define f(x, y) = output of M for input x on path y and g(x) = 2^{p(|x|)}, then f(x, 1)f(x, 2) ⋯ f(x, g(x)) is the leaf string of M on input x. Thus the languages in R_{m}^{p,bit}(B) are also interpreted as the languages “defined via leaf language B.”

The examples mentioned in the introduction show that NP = R_{m}^{p,bit}({0, 1}^{∗} · 1 · {0, 1}^{∗}), that ⊕ P = R_{m}^{p,bit}({0^{∗} · 1 · 0^{∗} · 1}^{∗} · 0^{∗} · 1 · 0^{∗}), and that there exists some language B, acceptable by a pushdown automaton with logarithmic pushdown size, such that PSPACE = R_{m}^{p,bit}(B).

The following definition is from [15].

2.2 Definition. An m-valued locally definable acceptance type is a set F of functions from {0, …, m − 1}^{r} into {0, …, m − 1} for some r ∈ {2, 3, 4, …}. Every locally definable acceptance type F corresponds to a complexity class, denoted by (F)P, in the following way: A language L belongs to (F)P if there exists a polynomial time nondeterministic machine M such that for every input x:

• (forming an evaluation scheme) M attaches during its computation on input x to every non-leaf node of the computation tree with r successors an r-ary function from F ∪ {id} (r ≥ 1) and to every leaf a value from {0, 1, …, m − 1}.

• (evaluating the scheme) The values of the leaves are given. The value of a non-leaf node with attached r-ary function f is f(a_{1}, a_{2}, …, a_{r}), when a_{1}, a_{2}, …, a_{r} are the values of the successors.

• (acceptance) x ∈ L if and only if the value of the root is 1.

It is easy to see that for all locally definable acceptance types F the relation (F)P ⊆ PSPACE holds. On the other hand we remark that e.g. ({AND, OR})P = ({NOR})P = PSPACE, ({OR})P = NP, and ({AND})P = co-NP.

The following observation is easy to see:

2.3 Proposition. For a class C, the following are equivalent:

1. There is a regular language B, such that C = R_{m}^{p,bit}(B).

2. There is an associative function f, such that C = ({f})P.

3 Closure of regular languages under polynomial bit-reductions

One can easily see that for every regular language B (and even for every B ∈ POLYLOGSPACE), R_{m}^{p,bit}(B) ⊆ PSPACE. In this section we exhibit a regular language B with the property that R_{m}^{p,bit}(B) = PSPACE.

The technique is very much inspired by the work of Barrington and Thérien [3, 4], who investigated regular languages and their meaning for the circuit class NC^{1}. We start with the fact that the group A_{5} of even permutations on five elements can in a certain way simulate a NOR-operation.

Let b, c, d, e, f be the following permutations from the group A_{5}:

\begin{matrix}b = & (23)(45), \\ c = & (12435), \\ d = & (243), \\ e = & (345), \\ f = & (152) \end{matrix}

Further let a_{0} be the empty permutation, denoted by a_{0} = (), and let a_{1} = (12345). Now consider the following product in A_{5} including the variables x and y:

w(x, y) = a_{0}bx^{4}cy^{4}dxeyf

Simple calculations show that w(a_{0}, a_{0}) = a_{1} and w(a_{0}, a_{1}) = w(a_{1}, a_{0}) = w(a_{1}, a_{1}) = a_{0}. Thus coding the value true by a_{1}, and false by a_{0}, we can view w as the NOR-operation applied to x and y.

Using the multiplication table of the group A_{5} as a binary function f_{A_{5}} over the 60 elements of A_{5} it is clear now that each polynomial time NOR-machine can be simulated by an f_{A_{5}}-machine: replace every appearance of a “NOR”-node with sons x and y in the computation tree by a binary subtree of height 4 whose 16 leaves are

a_{0} b x x x x c y y y y d x e y f

Now, since the function f_{A_{5}} clearly is an associative function, the root value of an f_{A_{5}}-machine merely depends on the leaf string, and it is equal to the product of the leaf values computed in A_{5}. Thus we accept the input if and only if the leaf string evaluates to a_{0}. Taking B to be the regular language {w | w is a string of elements from A_{5} which evaluates to a_{1}}, we then get R_{m}^{p,bit}(B) = (f_{A_{5}})P = ({NOR})P = PSPACE.

Thus we obtain:

3.1 Theorem. There is a regular language B, such that

PSPACE = R_{m}^{p,bit}(B) = R_{m}^{p,bit}(REG)

4 Normal forms for PSPACE

Some interesting consequences of our main theorem are given in the following corollary.

4.1 Corollary.

1. There is an associative function f such that PSPACE = ({f})P.

2. PSPACE is equal to the class of languages recognized by AC^{0}-uniform bounded width exponential size branching programs.

3. There is a homomorphism h over some suitable alphabet Σ such that PSPACE = R_{m}^{p,bit}(h(Σ^{∗})).

Proof. (Sketch )

1. Choose f = f_{A_{5}}.

2. Since a PSPACE-computation on an alternating Turing machine can be normalized in such a way that on every path at most one bit of the input is queried, we see that every permutation printed at a leaf of the f_{A_{5}}-tree constructed in the proof of Theorem 3.1 depends on at most one bit of the input. Thus the exponentially long string can directly be transformed into an exponentially long width 5 permutation branching program (see [3, 19]); and this permutation branching program can be transformed using standard techniques (see [19]) into a usual branching program without increase of width or depth by more than a constant factor. The AC^{0}-uniformity is a consequence of the fact that witness sets of nondeterministic polynomial time machines are in AC^{0}.

If we want to compute the i-th triple of the permutation branching program, we interpret i as an encoding of a configuration sequence corresponding to a path of the f_{A_{5}}-tree. If i encodes a correct sequence, then we output the index of the input bit which is queried and the two relevant permutations. If i does not encode a correct configuration sequence, we output a triple with empty permutations. All this can be done in AC^{0}.

3. The f_{A_{5}}-tree constructed in the proof of 3.1 yielded a leaf string w which evaluates to a_{1} iff the input is accepted. Modify the machine in such a way that it produces the leaf string wa_{1}^{−1}. This string evaluates to a_{0} (the unit element of A_{5}) iff the input is accepted. Now modify the machine in such a way that it produces a leaf string w′ which is constructed from wa_{1}^{−1} by inserting between any two neighbouring leaves the sequence a_{1}^{−1}a_{1}a_{2}^{−1}a_{2} ⋯ a_{59}^{−1}a_{59}. This string evaluates to a_{0} iff the input is accepted. Additionally, the value a_{0} appears in w′ as intermediate result (when multiplying from left to right) after at most 235 symbols. Let {t_{1}, t_{2}, …, t_{ℓ}} be the set of all words over A_{5} which have maximum length 235 and evaluate to a_{0}. Take some alphabet {b_{1}, b_{2}, …, b_{ℓ}} and a homomorphism h defined by h(b_{i}) = t_{i} for all i = 1, 2, …, ℓ. Consequently, w′ ∈ h(Σ^{∗}) iff the input is accepted.

□

Cai and Furst defined a class C to be C′-serializable if every computation for a language from C can be partitioned into an exponential number of local computations (which are restricted in power corresponding to the resource bounds of the class C′), each passing only a constant number of bits to the next local computation (see [9] for the details). The last Corollary directly yields the following:

4.2 Corollary. PSPACE is AC^{0}-serializable.

5 Subclasses of REG

Let SOLV denote the class of regular languages whose syntactic monoid is solvable (a monoid M is solvable if every subgroup of M is solvable), let SOLVGR denote the class of regular languages whose syntactic monoid is a solvable group, and let Br_{k} denote the k-th level of the Brzozowski hierarchy (dot depth hierarchy) of regular languages [10].

5.1 Theorem.

1. PSPACE = R_{m}^{p,bit}(B)

for every B ∈ REG \ SOLV.

2. MOD-PH = R_{m}^{p,bit}(SOLV).

3. MOD^{∗}P = R_{m}^{p,bit}(SOLVGR).

4. BC(Σ_{k}^{p}) = R_{m}^{p,bit}(Br_{k}).

The proof of this theorem, again very much inspired by the results of [4] about the circuit classes ACC and AC^{0}, is a bit technical and relies on a certain correspondence between the existential operator on complexity classes and the operation of concatenation between classes of leaf strings on the one side, and between modulo counting and multiplication in cyclic groups on the other side.

6 Polylogarithmic time bit-reducibili-ty

In order to study the classes of type R_{m}^{p,bit}(·) it is very useful to use a polylogarithmic time bitreducibility very similar to a definition from [7]:

6.1 Definition. The language A is polylogarithmic time bit-reducible to language B, A ≤_{m}^{plt,bit} B, iff there exist two functions f and g, computable in polylogarithmic time on a deterministic Turing transducer with random access to the input, where f is zero-one-valued, such that

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

It is obvious that ≤_{m}^{plt,bit} is a transitive relation, whereas ≤_{m}^{p,bit} is not. However, the following relationships hold:

6.2 Lemma. For every A, B, C,

if A ≤_{m}^{p,bit} B and B ≤_{m}^{plt,bit} C, then A ≤_{m}^{p,bit} C,

or, in other terms,

if B ≤_{m}^{plt,bit} C, then R_{m}^{p,bit}(B) ⊆ R_{m}^{p,bit}(C),

or, in other terms,

R_{m}^{p,bit}(R_{m}^{plt,bit}(C)) = R_{m}^{p,bit}(C).

This observation has already been made in [7] and, moreover, it has been proved there that the implication B ≤_{m}^{plt,bit} C ⇒ R_{m}^{p,bit}(B) ⊆ R_{m}^{p,bit}(C) actually becomes an equivalence if the right hand side holds in every relativized world; i.e. B ≤_{m}^{plt,bit} C if and only if for all oracles D, R_{m}^{p,bit}^{D}(B) ⊆ R_{m}^{p,bit}^{D}(C). Thus the inclusional relationships between the classes of type R_{m}^{p,bit}(B) which hold under every relativization are completely characterized by the ≤_{m}^{plt,bit}-structure of the leaf languages B.

7 Reductions to time-bounded classes

In this section we will prove results on R_{m}^{p,bit}(·), when the complexity of the leaf language is defined via time-bounds on a deterministic or nondeterministic Turing machine. Our proofs here will rely on padding techniques.

7.1 Definition. For a language A and a function r: IN → IN such that r(n) ≥ n for all n, let the rpadded version of A be

A(r) =_{def} { x10^{r(|x|)−|x|−1} | x ∈ A }.

We remark that if A is projection-reducible to B in the sense of [17], then A ≤_{m}^{plt,bit} B

We have the following relationship between the complexities of a set A and its 2^{n^{k}}-padded version.

7.2 Proposition. For every k ≥ 1, A ≤_{m}^{p,bit} A(2^{n^{k}}).

7.3 Proposition. For every t ≥ id, k ≥ 1,

A ∈ DTIME(t(2^{n^{k}})) implies A(2^{n^{k}}) ∈ DTIME(t∘Pol)

The previous propositions allow us to deduce the following equation.

7.4 Theorem. For every t ≥ id,

DTIME(t ∘ 2^{Pol}) = R_{m}^{p,bit}(DTIME(t ∘ Pol)).

Proof. Let A ∈ DTIME(t ∘ 2^{n^{k}}). By Propositions 7.2 and 7.3 we have A ≤_{m}^{plt,bit} A(2^{n^{k}}) ∈ DTIME(t ∘ Pol). The other direction follows directly by composing the ≤_{m}^{p,bit}-reduction with the t∘Pol-time bounded decision procedure. □

7.5 Corollary. For every t ≥ id, if B is ≤_{m}^{plt,bit}- complete for DTIME(t ∘ Pol) then

DTIME(t ∘ 2^{Pol}) = R_{m}^{p,bit}(B)

Proof. By the previous theorem and Lemma 6.2 we obtain

DTIME(t ∘ 2^{Pol}) = R_{m}^{p,bit}(DTIME(t ∘ Pol))
= R_{m}^{p,bit}(R_{m}^{plt,bit}(B))
= R_{m}^{p,bit}(B)
□

By exactly the same arguments, simply replacing in every statement of this section DTIME by NTIME, we can prove an analogue to 7.4 and 7.5 for nondeterministic classes:

7.6 Theorem. For every t ≥ id,

NTIME(t ∘ 2^{Pol}) = R_{m}^{p,bit}(NTIME(t ∘ Pol)).

7.7 Corollary. For every t ≥ id, if B is ≤_{m}^{plt,bit}- complete for NTIME(t ∘ Pol), then

NTIME(t ∘ 2^{Pol}) = R_{m}^{p,bit}(B)

7.8 Corollary.

1. If B is ≤_{m}^{plt,bit}-complete for P, then

DTIME(2^{Pol}) = R_{m}^{p,bit}(P) = R_{m}^{p,bit}(B)

2. If B is ≤_{m}^{plt,bit}-complete for NP, then

NTIME(2^{Pol}) = R_{m}^{p,bit}(NP) = R_{m}^{p,bit}(B)

Since most of the reductions in proofs of P- and NPhardness are indeed projections in the sense of [17] and therefore also ≤_{m}^{plt,bit}-reductions, these results give a lot of natural complete leaf languages characterizing exponential time classes.

7.9 Corollary.

1. DTIME(2^{Pol}) = R_{m}^{p,bit}(CIRCUIT-VALUE).

2.

NTIME(2^{Pol}) = R_{m}^{p,bit}(3-SAT)
= R_{m}^{p,bit}(CLIQUE)
= R_{m}^{p,bit}(COLOUR).

So using Cai and Furst’s expressions, we might say that DTIME(2^{Pol}) and NTIME(2^{Pol}) survive polynomial width bottlenecks.

8 Reductions to other classes

In completely the same way as for Theorem 7.4 we obtain:

8.1 Theorem. For every s ≥ log,

DSPACE(s ∘ 2^{Pol}) = R_{m}^{p,bit}(DSPACE(s ∘ Pol)).

8.2 Corollary.

PSPACE = R_{m}^{p,bit}(POLYLOGSPACE).

The class POLYLOGSPACE seems to be the largest class whose ≤_{m}^{p,bit}-closure is equal to PSPACE where the class REG marks the low end of the variety of those classes (cf. Theorem 3.1).

Again in the same way as for Theorem 7.4 we conclude:

8.3 Theorem. For X ∈ {D, N} and every s ≥ log and t ≥ id,

2-auxPD-XSPACE-TIME(s ∘ 2^{Pol}, t ∘ 2^{Pol}) = R_{m}^{p,bit}(2-auxPD-XSPACE-TIME(s ∘ Pol, t ∘ Pol)).

Taking into account the equations

2-auxPD-DSPACE-TIME(log, Pol) = R_{m}^{log}(DCFL)

and

2-auxPD-NSPACE-TIME(log, Pol) = R_{m}^{log}(CFL)

from [18], we obtain

8.4 Corollary.

2-auxPD-DSPACE-TIME(Pol, 2^{Pol}) = R_{m}^{p,bit}(R_{m}^{log}(DCFL))

2-auxPD-NSPACE-TIME(Pol, 2^{Pol}) = R_{m}^{p,bit}(R_{m}^{log}(CFL))

Because of

REG ⊆ R_{m}^{log}(DCFL)
⊆ R_{m}^{log}(CFL)
⊆ POLYLOGSPACE

we finally give a characterization of PSPACE via auxiliary pushdown automata; a result implicit in [13] and [8].

8.5 Corollary.

PSPACE = 2-auxPD-DSPACE-TIME(Pol, 2^{Pol})
= 2-auxPD-NSPACE-TIME(Pol, 2^{Pol})

As a last remark, we want to point out that using the methods from Section 7 it is also possible to prove a translational result relating ATIME(t ∘ 2^{Pol}) and ATIME(t ∘ Pol), which together with the results of [3, 4] is sufficient to prove Theorem 3.1 and Theorem 5.1. But since PSPACE was the starting point of our studies and since the normal forms from Section 4 (Corollaries 4.1 and 4.2) are stronger than what could be obtained in this way, we preferred to give an independent proof for that case.

9 Conclusion

In our view one of the major contribution of this paper is that it relates notions from complexity theory which at a first glance are rather different.

Our main goal was to study polynomial time bitreducibility, i.e. classes of the form R_{m}^{p,bit}(·).

There are relationships to the leaf language approach to define complexity classes: Language A defines the class C in the sense of Bovet, Crescenzi, and Silvestri [6, 7], if and only if C = R_{m}^{p,bit}(A). Two classes of type R_{m}^{p,bit}(·) are equal if the ≤_{m}^{plt,bit}-degrees of their leaf languages coincide.

There are relationships to Hertrampf’s study of locally definable acceptance types: Class C has an associative locally definable acceptance type in the sense of [14, 15] if and only if C = R_{m}^{p,bit}(B) for some regular language B. Our paper shows that a possible way to obtain a catalogue of all classes which are locally definable with associative functions is to study the ≤_{m}^{plt,bit}- reductions between regular languages, since there can be no more such classes that regular ≤_{m}^{plt,bit}-degrees.

There are relationships to circuit complexity: Completeness of classes of regular languages for subclasses of NC^{1} translate directly to completeness results for subclasses of PSPACE.

Acknowledgements

Thanks to Krzysztof Loryś (Wrocław) for informing us about Harju’s characterization of PSPACE via auxiliary pushdown automata; to Wolfgang Thomas (Kiel) for some useful information concerning string logic; and to Martin Böttcher (Mainz), Gerhard Buntrock (Würzburg), and Diana Emme (Würzburg) for fruitful discussions on the subject of this paper.

References

[1] J. L. Balcázar, J. Díaz, J. Gabarró, Structural Complexity I; Springer Verlag (Berlin – Heidelberg – New York, 1988).

[2] J. L. Balcázar, J. Díaz, J. Gabarró, Structural Complexity II; Springer Verlag (Berlin – Heidelberg – New York, 1990).

[3] D. A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC^{1}; J. Comput. Syst. Sci. 38 (1989), pp. 150–164.

[4] D. A. Mix Barrington, D. Thérien, Finite monoids and the fine structure of NC^{1}; J.ACM 35 (1988), pp. 941–952.

[5] R. Beigel, J. Gill, U. Hertrampf, Counting classes: thresholds, parity, mods, and fewness; Proceedings of the 7th Symp. on Theoretical Aspects of Computer Science (1990), LNCS 415, pp. 49–57.

[6] D. P. Bovet, P. Crescenzi, R. Silvestri, Complexity classes and sparse oracles; Proceedings of the 6th Structure in Complexity Theory Conference (1991), pp. 102–108.

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

[8] G. Buntrock, A. Hoene, Reversals and alternation; Proceedings of the 6th Symp. on Theoretical Aspects of Computer Science (1989), LNCS 349, pp.218–228.

[9] J.-Y. Cai, M. Furst, PSPACE survives constant-width bottlenecks; International Journal of Foundations of Computer Science 2 (1991), pp. 67–76.

[10] S. Eilenberg, Automata, Languages, and Machines, Vol. B; Academic Press (New York – San Francisco – London, 1976).

[11] H. Galperin, A. Wigderson, Succinct representations of graphs; Information & Control 56 (1983), pp. 183–198.

[12] S. A. Greibach, The hardest context-free language; SIAM J. Comput. 2 (1973), pp. 304–310.

[13] T. Harju, A simulation result for the auxiliary pushdown automata; J. Comp. Syst. Sci. 10 (1979), pp. 119–132.

[14] U. Hertrampf, Locally definable acceptance types—the three valued case; 1st Latin American Symp. on Theoretical Informatics (1992), LNCS 583, pp. 262–271.

[15] U. Hertrampf, Locally definable acceptance types for polynomial time machines; Proceedings of the 9th Symp. on Theoretical Aspects of Computer Science (1992), LNCS 577, pp. 199–207.

[16] J. E. Hopcroft, J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company (Reading, Mass., 1979).

[17] S. Skyum, L. G. Valiant, A complexity theory based on Boolean algebra; J. ACM 32 (1985), pp. 484–502.

[18] I. H. Sudborough, On the tape complexity of deterministic context free languages; J. ACM 25 (1978), pp. 405–414.

[19] I. Wegener, The Complexity of Boolean Functions; Teubner-Wiley (Stuttgart – Chichester – New York – Brisbane – Toronto – Singapore, 1987).