The Gap-Language-Technique Revisited

Heribert Vollmer Theoretische Informatik (FB 20) Johann-Wolfgang-Goethe-Universität D-6000 Frankfurt am Main

Abstract

Generalizing work of Schöning and others concerning gap language constructs recognizable in polynomial time we examine structural properties of reducibilities defined for various “lower” or “parallel” complexity classes. Finally we show how the proof techniques for the above can be used to show the existence of easy complexity cores for sets which cannot be decided in logarithmic space.

1 Introduction

In 1944, Post raised the question of whether there exists a recursively enumerable, non recursive non complete set. His question was answered independently and almost simultaneously in 1956/57 by Friedberg and Muchnik (see e. g. [11, 12]). Their results required a new proof technique which became known as the finite injury priority method.

An analogous subrecursive question in the P vs. NP-context, whether there exists a non polynomial-time decidable non NP-complete set in NP, was, in a sense (i. e. under the assumption P ≠ NP), solved in 1975 by Richard Ladner [7]. His result was generalized in several directions in the meantime in a number of papers [8, 5, 13], the last of them presenting what is nowadays called “The Uniform Diagonalization Theorem” [2]. This theorem allows in a fairly general context the construction of different polynomial time many-one degrees in various complexity classes.

The most extensive study of questions of the above kind was done by K. Ambos-Spies in [1]. Based on two diagonalization theorems (“diagonalization lemma” and “meet lemma”) a number of very interesting and fundamental results are proved about the degree structure of various polynomial time reducibilities.

But what remains open in the above cited papers is the question whether similar results hold for classes which are contained in P. A step in this direction was done by Diana Schmidt [15]. She obtained some results about the structure of logspace reducibility.

In this paper we also address the just mentioned question and first show, how to obtain slightly more elegant proofs of the results of [15] and how to translate the results of [1] in the logspace-context. Our proofs heavily depend on a refinement of the “gap language technique” introduced in [13].

Our technique doesn’t stop at logspace-reductions, but can be applied for so called constant-depth-reducibility, so we get results even for very low complexity classes (“parallel complexity classes”, because of their strong connection to parallel computation models as the PRAM), e. g.: Suppose TC^{0} ≠ NC^{1}, then there exist infinitely many cd-degrees between TC^{0} and NC^{1}. For classes which were separated in the past, for instance AC^{0} and TC^{0}, we definitely obtain (without any assumption in the above form) a rich structure of different degrees between them.

But our refinement of the gap language technique does not only lead us to simple and short proofs of results about logspace reducibility and constant-depth reducibility. Perhaps the most interesting application is the following:

Take any set A ∉ L. Then, for every Turing machine M deciding A, i.e. L(M) = A, there are infinitely many inputs w, such that M uses more than logarithmic space on these inputs. (Otherwise, M could be patched to work in logspace.) Can the two quantifiers in the last sentence be swapped? In other words, is there an infinite set X, such that any algorithm for A uses more than logarithmic space on almost all members of X? Such a set X is called a logspace complexity-core.

In the context of polynomial time, complexity-cores are very well examined. Lynch [9] showed the existence of a recursive (analoguously defined polynomial) complexity-core for every set A ∉ P. Orponen and Schöning [10] improved upon this result and showed the existence of a complexity-core for every A ∉ P, which itself is in DTIME(t(n)) for any time-constructible superpolynomial function t.

1988 Book et al. [3] examined complexity-cores in very general contexts for various complexity classes. They proved, concerning logspace, the existence of a recursive logspace complexity-core, but couldn’t bound it’s complexity, since the technique of [10], based on gap language methods, didn’t seem to be applicable in logspace. But our refinement used to show our first results is strong enough for this kind of theorem, too. We present for any given set A ∉ L a logspace complexity core X, which is “arbitrarily close” to L. I.e. the members of X are hard with respect to membership in A, but membership in X itself can be decided easily.

In the next section, we will present the relevant definitions and our refinement of the gap language technique. Then we will proceed demonstrating how to obtain structural results about logspace reducibility. In section 4 we will address the question of complexity cores. In section 5 we will generalize our results from section 3 to constant-depth reducibility, and finally, in the last section, we will give a short conclusion.

2 Definitions

We assume the reader is familiar with standard complexity classes and complexity theory notions, as time and space bounded classes (L, NL, P, NP), reduciblity concepts (especially logspace-reducibility) and their properties. Our notation here is standard (see for example [2]). Further we presuppose some basic knowledge about parallel complexity classes like AC^{0}, TC^{0}, NC^{1} and NC, and the reducibility concepts involved here [4, 6].

2.1 Constructibility

Every one familiar with complexity theory knows about the concept of space- or timeconstructibility. Here we need a slightly refined definition.

(2.1) Definition: A function f: IN → IN is said to be strongly space-constructible if and only if f is computable in space log ∘f.

This means that there is a Turing machine M computing f which on input n uses no more than log f(n) tape cells, i.e. the space needed by M is bounded above by the logarithm of the value of the output of M; or in other words, M uses no more tape cells than are needed to write down f(n) (which can be done in space log f(n)).

That this is not a too severe restriction is the claim of the following lemma.

(2.2) Lemma: For each function f: IN → IN there is a function f′ ≥ f, which is strongly space-constructible.

Proof. Choose f_{1} ≥ f to be space-constructible in the traditional way. Let M be the Turing machine witnessing this fact.

Define a Turing machine M′ to operate as follows:

input x: compute f_{1}(x) by simulating M(x); print 2^{f_{1}(x)}.

Let f′ = f_{M′}.

Clearly f′(x) ≥ f(x) for all inputs x; and M′ operates in space f_{1}(x) = log f′(x), since the simulation of M on input x requires exactly f_{1}(x) tape cells. □

The following notion was implicit in [7, 8] and first defined explicitly by Schöning in [13].

Let f^{(n)} denote the function obtained by n-fold application of f.

(2.3) Definition: For a given recursive function f, such that f(n) > n for all n ∈ IN, define the language G[f] to be

G[f] = {x ∈ Σ^{⋆} | f^{(n)}(0) ≤ |x| < f^{(n+1)}(0) for some n ≡ 0 (mod 2)}

If we require the parameter function f in our language G[f] to be constructible in the above sense, we get the following result, which we will often use in the future.

(2.4) Lemma: If f: IN → IN is strongly space-constructible and f(n) > n for all n ∈ IN, then G[f] ∈ L.

Proof. Let M be the machine showing the constructibility of f. Consider the following Turing machine M′:

On input x, |x| = n, first M′ marks exactly log n tape cells. (This can be done reading x from left to right, counting the length of x, and upon reading the last symbol of x marking the space used by the counter.) Now consecutively compute 0, f(0), f(f(0)), … by simulating M, until some k is found which satisfies f^{(k)}(0) ≤ n < f^{(k+1)}(0). Accept if and only if k ≡ 0 (mod 2). To compute 0, f(0), f(f(0)), …, f^{(k)}(0), which are all less than n, we surely need no more space than log n. In computing f^{(k+1)}(0), which can be considerably greater than n, we just have to wait, until machine M tries to leave the marked region. Then we know for sure, that f^{(k+1)}(0) will be greater than 2^{log n}.

Since in all these computations the same space can be used, M′ doesn’t exceed the resource bounds of the class L. □

2.2 Presentability

(2.5) Definition: A language class C is recursively presentable, if and only if there is an effective enumeration M_{1}, M_{2}, M_{3}, … of deterministic and total Turing machines, such that C = {L(M_{i}) | i ≥ 1}.

Nearly all “reasonable” complexity classes are recursively presentable [13]. We are especially interested in the following cases.

(2.6) Lemma: The following classes are recursively presentable:

1. L, P

2. NC

3. the set of P-complete problems under logspace-reductions.

Proof. Similar to the results in [13]. □

3 The degree structure of logspace reducibility

We only state now that the results from the preceding section allow us to prove all of the well-known diagonalization theorems mentioned in the introduction for logspace (instead of polynomial time); and these theorems lead us to a number of very interesting structural properties of logspace reducibility. All these results are obtained in a completely analogous way to the proofs of [1].

For concreteness we only state (without proofs) the most simple and direct results, some of which are already present in [15].

(3.1) Corollary: Suppose P ≠ L. Then there exists a language L ∈ P which is neither logspace-complete for P nor in L.

An analogous result holds for the class NC:

(3.2) Corollary: If P ≠ NC, then there exists a language L ∈ P, which is neither logspace-complete for P nor in NC.

So we get the existence of problems which are not efficiently parallelizable but also not P-complete.

Let ℵ_{0} denote the cardinality of the set of natural numbers.

(3.3) Corollary: There is a rich structure of ℵ_{0} different ≤L_{m}-degrees between P and L (assuming P ≠ L).

(3.4) Definition: Two sets A_{1}, A_{2} form a minimal pair for L if and only if A_{1} and A_{2} are not in L and every set logspace-reducible to both A_{1} and A_{2} is in L.

(3.5) Corollary: There is a minimal pair for L, which can be decided in P (assuming P ≠ L).

(3.6) Corollary: There is a minimal pair for NC under logspace reductions, which can be decided in P (assuming P ≠ NC).

For more subtle and far-reaching questions, concerning among others a generalization of the last corollaries (“meet lemma”) and a general result about lattice embeddings into the partial ordering of the logspace degrees, the interested reader is refered to [1] and asked to translate the results given there from the polynomial time context into the logspace context.

4 Complexity Cores

In this section we apply our generalized gap language technique to another problem:

(4.1) Definition: Let A be recursive and X be of infinite cardinality. We call X a logspace complexity-core for A, if and only if for every Turing machine M deciding A and every c ∈ IN,

|{x ∈ X | space_{M}(x) ≤ c log |x|}| < ∞.

Here space_{M}(x) denotes the number of tape cells, which M uses on input x.

(4.2) Definition: H(M, s) = {x | space_{M}(x) > s(|x|)}.

I.e. X is a logspace complexity-core for A, if and only if for all Turing machines M deciding A and c ∈ IN,

{x ∈ X | x ∉ H(M, λn.c log n)} = X − H(M, λn.c log n)

is finite. (We use Church’s lambda-notation to define functions from terms. If t(x) is a term with free variable x, then λx.t(x) denotes the associated partial function.)

In the proof of our result, we need a very special kind of enumerating Turing machines for some language.

(4.3) Lemma: Let A be recursive.

There is an enumeration ⟨M_{i}⟩ of deterministic and total Turing machines, such that:

1. For all i ≥ 1, L(M_{i}) = A or |L(M_{i})| < ∞.

2. For all i ≥ 1, if |L(M_{i})| < ∞, then |\overline{H(M_{i}, λn.c log n)}| < ∞.

3. For all Turing machines M, such that L(M) = A, and all c ∈ IN, there are i, c′ ∈ IN,

such that

H(M_{i}, λn.c′ log n) ⊆ H(M, λn.c log n).

Proof. Let A = L(M_{0}) for some Turing machine M_{0}; and let s(n) ≥ n be a spaceconstructible space-bound of M_{0}. Let ⟨N_{i}⟩ be an enumeration of all Turing machines operating in space s.

Now define:

M_{i}(x), |x| = n: if ∀y, s(|y|) ≤ 2^{n}: y ∈ L(M_{0}) ⇔ y ∈ L(N_{i}) then simulate N_{i}(x) else mark n tape cells and reject.

Propositions (1) and (2) are immediate. Now take any M, L(M) = A, and any c ∈ IN and define:

M′(x):

simulate in parallel M_{0}(x) and M(x); if any of the two stops, then

stop and reject or accept according to this machine.

Since M_{0} operates in space s, M′ also operates in space s. So M′ = N_{i} for some i. Now, machine M_{i} uses (for some c′) no more than c′ log n tape cells on those inputs of length n, which are accepted by N_{i}. All in all we have:

H(M_{i}, λn.c′ log n) ⊆ H(N_{i}, λn.c log n) = H(M′, λn.c log n) ⊆ H(M, λn.c log n);

so our enumeration fulfills property (3). □ Our result now is:

(4.4) Theorem: Let A be a recursive set not in L. Then A has a logspace complexity core X ∈ DSPACE(s(n)) for any superlogarithmic space-constructible function s.

Proof. Let ⟨M_{i}⟩ be the enumeration of the previous lemma. Define

f(j) = (μk > j)(∃x, |x| = k: j log k ≤ s(k) ∧ ∀i ≤ j: x ∈ H(M_{i}, λn.j log n).

f is total, since for all j,

⋂_{i=1}^{j} H(M_{i}, λn.j log n)

is infinite (otherwise combining the M_{i}s, i ≤ j, would show A ∈ L, in contradiction to our assumption).

Let g ≥ f be strongly space-constructible. Define a Turing machine M to operate as follows: input x, |x| = n:

let k = g^{(m)}(0), where g^{(m)}(0) < |x| ≤ g^{(m+1)}(0);
accept iff k log n ≤ s(n) ∧ ∀i ≤ k: x ∈ H(M_{i}, λn.k log n).

Now let X = L(M).

The computation of k needs only logspace, so surely X ∈ DSPACE(s(n)).

X is infinite, since for all m, there is one x of length between g^{(m)}(0) and g^{(m+1)}(0), which is accepted by M. This follows from the definition of f.

Let M be any machine deciding A, and let c ∈ IN. Since for every i and every c′ ∈ IN, all but finitely many x ∈ X are in H(M_{i}, λn.c′ log n), X − H(M, λn.c log n) is finite by the lemma from the last section; and hence X is a complexity core for A. □

5 Inside NC

The reducibility notion used in the preceding sections was that of logspace reducibility. In this section we show how our results apply even for some very strong notion of reducibility, i.e. that of constant-depth reduciblity. Thus our techniques apply within NC and even within NC^{1}.

We first define a very strong constructibility notion.

(5.1) Definition: Call a function f: IN → IN strongly time-constructible, if and only if f can be computed in time log ∘f (i.e. in time logarithmic in the value of the output).

In other words: f is strongly time-constructible if the time needed to compute f is dominated by the time needed to write down the output.

Still, these functions can majorize every other recursive function.

(5.2) Lemma: For every recursive function f: IN → IN, there is a strongly time-con-structible function f′ ≥ f.

Proof. Analogously to the corresponding lemma in section 2. □

(5.3) Lemma: Suppose f is strongly time-constructible and f(n) ≥ n^{1+ε} for all n ∈ IN and for some fixed ε > 0. Then G[f] ∈ LT, i.e. G[f] can be computed in logarithmic time by a deterministic Turing machine with a random access input tape.

Proof. On input x, first compute n = |x|. An indexing Turing machine can do so in time log |x| by one-sided binary search [17]. Then again compute 0, f(0), f(f(0)), …, until some k is found s.t. f^{(k)}(0) ≤ |x| < f^{(k+1)}(0). What is the time needed for this procedure? The time to calculate f^{(k)}(n) is surely ≤ log n. Since f(n) ≥ n^{1+ε}, we have f^{(k−1)}(0) ≤ n^{1/(1+ε)} and therefore the time needed to compute this value is at most 1/(1 + ε) log n. Repeating this argument we see that the whole time needed is at most

log n + ∑_{i=0}^{k} \frac{1}{(1 + ε)^{i}} log n = O(log n).

□

In this section we want to obtain results for parallel complexity classes, for instance for TC^{0} and NC^{1}; so we are interested in cd-reducibility. But it will be convenient not to use these reductions directly but to introduce yet another, even stronger, reducibility:

(5.4) Definition [17]: A ≤LT_{m} B if and only if there is a function π: Σ^{⋆} → Σ^{⋆} with the following properties:

1. x ∈ A ⟺ π(x) ∈ B.

2. |π(x)| ≤ p(|x|) for some polynomial p.

3. The function φ(x, i) = the i-th bit of π(x) is computable in logarithmic time by a deterministic indexing Turing machine.

(5.5) Proposition: A ≤LT_{m} B ⟹ A ≤_{cd} B

Proof. A logtime Turing machine can be simulated by a poly-size constant depth circuit by brute force. Combine the machines for different bits and feed them as input to an oracle gate. □

So the results mentioned in section 3 even translate to very low complexity classes (since the gap constructs now can be recognized in logarithmic time). A rich structure of different degrees exists between classes like AC^{0}, TC^{0}, NC^{1}, L, NL, NC^{2}, NC^{3} etc.

6 Conclusion

We presented a refinement of Schöning’s gap language technique [13] and applied it in the contexts of degree structure of subpolynomial reducibilities and complexity cores. Thus we extended results of [7, 13, 14, 1, 15, 10, 3]. It should be mentioned that parts of our results of the first sections were obtained independently and almost simultaneously by M. Serna in [16]. In this paper, and also in the paper of D. Schmidt [15], on which [16] is based, a complicated condition called “recursive gap closed” is required to be shown before applying Schöning’s technique. We drop this condition and require instead “strong constructibility” of the functions used. We think that this condition is more intuitive and easier to prove. We thus obtain stronger results.

Another advantage of our approach is that besides examining structural properties of subpolynomial reducibilities it also permits some other application of the gap language technique, concerning complexity cores, as presented in section 4. We obtain all these results in a uniform manner, relying in all cases on strong constructibility.

Our paper shows that some very familiar techniques and problems in the P vs. NP context, e.g. constructibility, are not dependent on the question of the power of nondeterminism versus determinism, but also appear in very different other settings; so they seem to be instances of a more general principle. This we believe opens the door to serious complexity theory research about the so called parallel complexity classes, which evolved in the recent past and are of immense importance in the theory of algorithms.

References

[1] K. Ambos-Spies, Polynomial time degrees of NP-sets; in: E. Börger, Trends in Theoretical Computer Science, Computer Science Press, Rockville 1988, 95–142.

[2] J. L. Balcázar, J. Díaz, J. Gabarró, Structural Complexity I; Springer, Berlin, 1988.

[3] R. Book, D.-Z. Du, D. Russo, On polynomial and generalized complexity cores; Proc. 3rd Structure (1988), 236–250.

[4] A. K. Chandra, L. Stockmeyer, U. Vishkin, Constant depth reducibility; SIAM J. Comput. (13) (1984), 423–439.

[5] P. Chew, M. Machtey, A note on structure and looking back applied to the relative complexity of computable functions; J. Comput. System Sci. 22 (1981), 53– 59.

[6] S. A. Cook, A taxonomy of problems with fast parallel Algorithms; Inf. & Contr. 64 (1985), 2–22.

[7] R. E. Ladner, On the structure of polynomial time reducibility, J. ACM 16 (1975), 155–171.

[8] L. H. Landweber, R. J. Lipton, E. L. Robertson, On the structure of sets in NP and other complexity classes; Theoret. Comput. Sci. 1 (1975), 103–123.

[9] N. Lynch, On reducibility to complex or sparse sets; J.ACM 22 (1975), 341–345.

[10] P. Orponen, U. Schöning, The density and complexity of polynomial cores for intractable sets; Inf. & Contr. 70 (1986), 54–68.

[11] H. Rogers Jr., Theory of Recursive Functions and Effective Computability; McGraw-Hill, New York, 1967.

[12] R. I. Soare, Recursively Enumerable Sets and Degrees; Springer, Berlin, 1986.

[13] U. Schöning, A uniform approach to obtain diagonal sets in complexity classes; Theoret. Comput. Sci. 18 (1982), 95–103.

[14] U. Schöning, Minimal pairs for P, Theoret. Comput. Sci. 31 (1984), 41–48.

[15] D. Schmidt, The recursion-theoretic structure of complexity classes; Theoret. Comput. Sci. 38 (1985), 143–156.

[16] M. Serna, The parallel approximability of P-complete problems; Tesis doctoral, Facultat d’Informàtica de Barcelona (1990).

[17] J. Torán, Structural properties of the counting hierarchies; Tesis doctoral, Facultat d’Informàtica de Barcelona (1988).