Computational Complexity of Functions^{∗}

Leonid A. Levin^{†} Boston University^{‡}

Abstract

Below is a translation from my Russian paper. I added references, unavailable to me in Moscow. Similar results have been also given in [Schnorr Stumpf 75] (see also [Lynch 75]). Earlier relevant work (classical theorems like compression, speed-up, etc.) was done in [Tseitin 56, Rabin 59, Hartmanis Stearns 65, Blum 67, Trakhtenbrot 67, Meyer Fischer 72].

I translated only part with the statement of the results. Instead of the proof part I appended a later (1979, unpublished) proof sketch of a slightly tighter version. The improvement is based on the results of [Meyer Winklmann 78, Sipser 78]. Meyer and Winklmann extended earlier versions to machines with separate input and working tape, thus allowing complexities smaller than input length (down to its log). Sipser showed the space-bounded Halting Problem to require only additive constant overhead. The proof in the appendix below employs both advances to extend the original proofs to machines with fixed alphabet and separate input and working space. The extension has no (even logarithmic) restrictions on complexity and no overhead (beyond additive constant). The sketch is very brief and a more detailed exposition is expected later: [Seiferas Meyer].

My work on this extension, as well as my smooth implantation into the Western scientific community was made possible by comprehensive support and encouragement by Albert Meyer in 1978-80. I am among the many greatly indebted to his concern and generosity.

Some Remarks

We formulate the theorems in terms of Turing Machine space. But it is clear how to generalize them, since any complexity measure is bounded by a total recursive function (t.r.f.) of any other one. Of course, the accuracy of a constant factor will turn in to the accuracy of some other t.r.f. We consider one tape Turing Machines with arbitrary tape alphabets. If the alphabet has n symbols, then input and output integers are written in n-ary number system. The space p_{A}(x) of an algorithm A is the size [reduced by 1] of the tape used by A(x). The length of a word x is denoted l(x). Obviously, p_{A}(x) + 1 ≥ max(l(x), l(A(x))).

The space complexity of any function can be reduced by any constant factor, by extending the alphabet. The inequality within a constant factor f ≺ g means ∃C∀x f(x) ≤ Cg(x).

Every function F is associated with a class of algorithms which compute it and with the class of their space complexities M_{F}. We characterize all such classes extending well known Compression and Speed-up theorems. Some computable functions do not belong to any class M_{F}:

Note: A partial function p can be a space of an algorithm if and only if it is itself computable within space p(x). We call such functions simple. This requirement is weak since usual functions p are computable in space l(p(x)) = log p(x).

We call simple an algorithm which outputs its own space. We define p_{A}(x) = ∞, when A(x) does not halt and interpret inequalities with simple functions accordingly. Let us agree that an algorithm computes a function F, if it does this everywhere in the intersection of its domain and the domain of F.

∗Theoretical Computer Science, A 157, 1996. Partial translation from [Levin 74] (preliminary version is in [Levin 73]).

†Supported by NSF grant CCR-9015276.

‡Computer Science department, 111 Cummington St, Boston, MA 02215; (e-mail to Lnd@bu.edu).

Formulation of the Theorems.

Compression Theorem [Rabin], for any simple function G, provides a function F, computable in exactly those spaces p which are simple and p ≻ G. We generalize this theorem for an arbitrary recursive G:

Theorem 1 For any t.r.f. G there exists a t.r.f. F, with range {0, 1} computable in exactly those spaces p which are simple and p ≻ G.

Compression Theorem describes a very special case of t.r.f. In [Blum] t.r.f. were discovered which have no such exact simple lower bounds of complexity. However, the above generalization of the Compression Theorem describes already the general case and can be inverted as follows:

Theorem 2 For any t.r.f. F there exists a t.r.f. G such that F is computable in exactly those spaces p which are simple and p ≻ G.

Thus, the complexity class of any t.r.f. is organized naturally, despite the Speed-up theorem. The point is that the set of t.r.f. is richer than the set of simple functions. Naturally, the complexity of an arbitrary t.r.f. cannot be always characterized by a simple function, though it is always characterizable by a t.r.f. Let us describe the properties of the complexity classes for arbitrary t.r.f. A class M is called canonical if:

1. All functions of M are simple, and some of them are total and

2. If f, g, h are simple, f, g ∈ M, and h ≻ min(f, g), then h ∈ M and

3. The class \overline{M} of simple algorithms, computing the functions of M, is of type Σ_{2}^{0}, i.e. can be defined as (p ∈ \overline{M}) ⟺ ∃a∀b R(a, b, p), where R is recursive.

Theorem 3 M is the class M_{F} of all space complexities of some t.r.f. F iff M is canonical.

This theorem justifies the following conjecture of A.N. Kolmogorov: for any “good” decreasing sequence of functions p_{i} there exists a function, computable with such and only such space complexities, which exceed some of the p_{i}’s. The Compression and Speed-up theorems are special cases. This conjecture also describes the general case of complexity as it follows from Lemma 1 below and Theorem 3. The above results extend to the case of partial functions:

Theorem 4 Let A be an r.e. set. Theorems 1-3 remain valid, if the term “t.r.f.” is replaced everywhere by “partial r.f. with domain A”, and inequalities like “a ≻ b” are restricted to x ∈ A.

Proofs.

We call A-canonical a class M, satisfying conditions 1-3, as adjusted in Theorem 4.

Lemma 1 For any A-canonical M, a p.r.f. g exists, non-increasing with k and such that g(k, x) + l(k) is simple, domain of g(0, x) is A and p ∈ \overline{M} ⟺ (∃k g(k, x) ≺ p(x)), for any simple p.

[…]

Appendix (not part of the translation).

Below is the sketch of proof of a slightly tighter statement. It assumes separate input and working space, thus allowing spaces o(|x|), as in [Meyer Winklmann 78]. It also assumes a fixed tape alphabet, allowing additive (rather than multiplicative) constant accuracy. The latter uses [Sipser 78] result that space s bounded halting problem can be solved in space s + O(1). Otherwise the version is similar to the above translation. For log of time of Pointer Machine or of some Turing Machine versions [Levin 91] similar results hold.

Model. To allow space limits below the input bit-length |x| one needs to differentiate the input symbols from symbols used as memory during the computation. Instead of separating the input tape as in [Hartmanis Stearns 65], I prefer to separate the “ink”. While not essential, this preserves the simple space-time geometry of the one-tape Turing Machine (TM). So, we separate the state of each cell into a read-only ink and a readwrite pencil part. The ink part cannot be modified after the input is written and is ignored for measuring space. The ink (but not necessarily pencil) string starts at the left end of the tape after exactly one blank. The ink and pencil string and their union form each a continuous segment without blanks. The alphabet is fixed and has at least two symbols {0, 1} besides blank. Space: S_{A(x)} or S_{A}(x) is the supremum of bit-lengths of the pencil string throughout the computation of A(x). The output may either be left on the tape/head or its digits “flashed” sequentially at the (fixed) leftmost cell. In some cases the pencil string starts not empty. E.g. g-constructible functions f are those computable in space max{t, f(x)} starting from input x and any pencil string of length t ≥ g(x); for g = 0 we omit the prefix “g-” and replace it for g = f with “semi-”.

Conventions. Let U(k, x) be a Universal TM with {0, 1} outputs. It ignores the “padding” k_{2} in its program k = (k_{1}, k_{2}). Appropriate paddings can put any Σ_{2}^{0} program set in the form m = a^{−1}({∞}) for some function a with constructible a(k) − 4|k|. Let p(k, x) =^{def} 4|k| + S_{U}(k, x) and expressions like p_{k}(x) mean p(k, x). Assume 0 ∈ m and M = \{p_{k} : k ∈ m\}. Consider the closure \overline{M} of a set M of functions under inclusion of each h s.t. for some f, g ∈ M, h ≥ min{f, g} − 1 in the domain D of U(0, x). Call sets M_{1}, M_{2} confinal if their closures contain the same constructible functions. Define [a < b] as a, if a < b and 0 otherwise. Likewise for ≤. Clearly, the complexity class of any function can be described as \overline{M} above.

Construction. Now we build (cf. Lemma 1) a monotone sequence g_{k} confinal to M: If a(k) > t > p(k, x), let p^{t}(k, x) =^{def} max_{l<k}{p(k, x), [a(l) ≤ t]} ≤ t. Otherwise, p^{t}(k, x) =^{def} t. Then, g(1, x) =^{def} p(0, x); g(k+1, x) =^{def} p^{g(k,x)}(k, x); g_{∞}(x) =^{def} min_{k} g(k, x); k_{x} =^{def} min{l : g(l, x) = g(k, x)}. To compute g_{k}(x) we carry k, g_{k−1}(x) as the pencil string length, and the largest relevant a(l) as g_{k−1}(x)−a(l) (if < 2|k|) or as l. Cutting the values of p, a to the maximum of t would not affect those values of g below t. So, g(k, x)−2|k_{x}| is g_{∞}-constructible; g_{k} are uniformly recursive with domain D and equal min_{l<k}{p_{l}(x) : l ∈m}, on D, except when both are ≤ max_{l<k}{[a(l) < ∞]} = O(1).

Next we convert such {g_{k}} into a confinal set consisting of a single semiconstructible recursive function G on D (cf. Theorem 2): Let b(k) =^{def} min_{x}(2|k, x| + g_{1}(x) : g_{k}(x) > p_{k}(x)) and K(x) =^{def} min{k : b(k) > g_{k}(x) > p_{k}(x)}. Then G(x) =^{def} g(K(x), x) ≤ max_{l≤k}{g(k, x), [b(l) < ∞]}, for all k. Conversely, G < p_{k} in D implies b(k) = ∞. Indeed, b(k) = 2|k, x| + g_{1}(x) < ∞ while g_{k}(x) > p_{k}(x) yields K(x) ≤ k and G(x) ≥ g_{k}(x) > p_{k}(x). b(k) = ∞ makes g_{k}(x) ≤ p_{k}(x) in D and p_{k} ∈ \overline{M}.

Finally, for such G, we build a G-constructible predicate Π(x) =^{def} 1 − U(K′(x), x) with complexity class confinal to G (cf. Theorem 1): Here K′(x) =^{def} min{k : c(k) > G(x) ≥ p_{k}(x)} and c(k) =^{def} min_{x}{2|k, x| + p_{0}(x) : K′(x) = k}.^{1} If Π(x) = U(k, x) in D then k ∉ K′(D) and c(k) = ∞. Then G(x) ≤ max_{l<k}\{p_{k}(x), [c(l) < ∞]\} and p_{k} ∈ \overline{M}.

1A leaner version: c(k) =^{def} min_{x}{2|k, x| + max{p_{0}(x), p_{k}(x)} : Π(x) ≠ U(k, x)}.

References

[1] M. Blum. A machine-independent theory of the complexity of recursive functions. J. ACM 14(2):322– 336, 1967.

[2] J. Hartmanis, R.E. Stearns. On the computational Complexity of Algorithms. Trans. AMS 117:285-306, 1965.

[3] L. Levin. On Storage Capacity for Algorithms. DAN SSSR = Soviet Math. Dokl. 14(5), 1973.

[4] L. Levin. Computational Complexity of Functions. In Complexity of Algorithms and Computations, pp. 174-185. Eds. V.A.Kosmidiadi, N.A.Maslov, N.V.Petri. “Mir,” Moscow, 1974.

[5] L. Levin. Theory of Computation: How to Start. SIGACT News, 22(1):47-56, 1991.

[6] N. Lynch. “Helping”: Several formalizations. J. Symb. Logic 40(4):555–566, 1975.

[7] A.R. Meyer and P. C. Fischer. Computational speed-up by effective operators. J. Symb. Logic 37(1):55– 68, 1972.

[8] A.R. Meyer and K. Winklmann. The fundamental theorem of complexity theory (preliminary version). In Foundations of Computer Science III, Part 1: Automata, Data Structures, Complexity, pp. 97–112. Eds. J.W. de Bakker and J. van Leeuwen. Mathematical Centre Tracts 108, Amsterdam 1979. Also a draft, 1978.

[9] C.P. Schnorr and G. Stumpf. A characterization of complexity sequences. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 21(1):47–56, 1975.

[10] J.I. Seiferas. Machine-independent complexity. In Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity, pp. 163–186. Ed. J. van Leeuwen. Elsevier Science Publishers and The MIT Press, 1990.

[11] Joel I. Seiferas and Albert R. Meyer. Characterization of Reliable Space Complexities. In preparation.

[12] M. Sipser. Halting space-bounded computations. Theor. Comp. Sci. 10(3):335–338, 1980. Also, FOCS-1978.

[13] M. Rabin. Speed of computation and classification of recursive sets. Third Conv. Scient. Societies 1-2, Israel, 1959; (also Tech. Rep. 3, Hebrew Univ., Jerusalem, 1960).

[14] B.A. Trakhtenbrot. Complexity of algorithms and computations. Course notes in Russian. Novosibirsk University, USSR, 1967.

[15] G.S. Tseitin. Talk: on Math. Logic Seminar, Moscow University, 1956. Also pp. 44-45 in S.A. Yanovskaya, Math. Logic and Foundations of Math., Math. in the USSR for 40 Years, 1:13-120, 1959, Moscow, Fizmatgiz, (in Russian).