\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 $<t$ volume of computation. Let $P_f(x)$ be the
smallest $i$, with $2K_t(i/x)>\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}).