2.3 Intractability; Compression and Speed-up Theorems.

The t-restriction of u aborts and outputs 1 if does not halt within steps, i.e. computes the t-Bounded Halting Problem (t-BHP). It remains complete for the class of functions computable within steps which is closed under negation. So, does not belong to the class, i.e. requires more time than o(t(x)) [Tseitin 55]. E.g.\ -BHP requires exponential time. For similar reasons any function which agrees with t-BHP on a dense (i.e. having strings with each prefix) subset cannot be computed in steps either.

On the other hand, we know that for some trivial input programs the BHT can be answered by a fast algorithm. The following Compression Theorem [Rabin 59] provides another function P_f (that can be made a predicate) for which there is only a finite number of such trivial inputs. The theorem is stated for the volume of computation for Multi-Head Turing Machine. It can be reformulated in terms of time of Pointer Machine and space (or, with smaller accuracy, time) of regular Turing Machine.

Definition: A function f(x) is constructible if it can be computed in volume V(x)=O(f(x)).

Here are two examples: 2^|x| is constructible, as V(x)=O(|x|log|x|) << 2^|x|. Yet, 2^|x| + h(x), where h(x) is 0 or 1, depending on whether U(x) halts within 3^|x| steps, is not.

Theorem: For any constructible function f, there exists a function P_f such that for all functions t, the following two statements are equivalent:

1. There exists an algorithm A such that A(x) computes P_f(x) in volume t(x) for all inputs x,.
2. t is constructible and f(x)=O(t(x)).

Let t-bounded Kolmogorov Complexity of x given y be the length of the shortest program p for the Universal Multi-Head Turing Machine transforming y into x with <t volume of computation. Let be the smallest i, with for all t. can be computed in volume f by generating all i of low complexity, sorting them and taking the first missing. It satisfies the Theorem, since computing i faster causes a violation of complexity bound defining it.

Speed-up Theorem.

This theorem will be formulated for exponential speed-up, but it remains true if log is replaced by any computable unbounded monotone function [Blum 67].

Theorem: There exists a total computable predicate P such that for any algorithm computing P(x) with running time t(x), there exists another algorithm computing P(x) with running time O(log t(x)).

This procedure may continue any constant number of steps. In other words, there is no even nearly optimal algorithm for the predicate P.

So, the complexity of some predicates P cannot be characterized by a single constructible function f, as in Compression Theorem. However, the Compression Theorem can be generalized by removing the requirement that f is constructible (it still must be computable or its subgraph enumerable). In this form it is general enough so that every computable predicate (or function) P satisfies the statement of the theorem with an appropriate computable function f. There is no contradiction with Blum's Speed-up Theorem, since the complexity f cannot be reached (f is not constructible itself). See a review in [Seiferas, Meyer].

Rabin's predicate has an optimal algorithm. Blum's does not. In general, one can't tell whether a computable predicate has an optimal algorithm or not (see the Rice-Uspenskii Theorem in Sec. 2.2).