\newpage\subsection {Intractability; Compression and Speed-up Theorems.} \label{compress} The {\em $t$-restriction} $u_t$ of $u$ aborts and outputs $1$ if $u(x)$ does not halt within $t(x)$ steps, i.e. $u_t$ computes the {\em $t$-Bounded Halting Problem ($t$-BHP)}. It remains complete for the class of functions computable within $o(t(x))$ steps which is closed under negation. So, $u_t$ does not belong to the class, i.e.\ requires time $\Omega_\infty(t(x))$ [Tseitin 56]. E.g.\ $2^{\|x\|}$-BHP requires exponential time. For similar reasons any function which agrees with $t$-BHP on a {\em dense} (i.e.\ having strings with each prefix) subset cannot be computed in $o(t(x))$ 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(x)$ (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. {\bf Definition}: A function $f(x)$ is {\em 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\|) \ll 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. {\bf Theorem:} For any constructible function $f$, there exists a function $P_f$ such that for all functions $t$, the following two statements are equivalent: \begin{enumerate} \item There exists an algorithm $A$ such that $A(x)$ computes $P_f(x)$ in volume $t(x)$ for all inputs $x$. \item $t$ is constructible {\em and} $f(x)=O(t(x))$. \end{enumerate} Let $t${\em-bounded Kolmogorov Complexity} $K_t(i/x)$ of $i$ given $x$ be the length of the shortest program $p$ for the Universal Multi-Head Turing Machine transforming $x$ into $i$ with $\log(f(x)/t)$ for all $t$. $P_f$ 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=P_f(x)$ faster causes a violation of complexity bound defining it. \subsubsection* {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]. {\bf 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$. \vspace{1pc} 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.~\ref{rec}).