# How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones?

I'm trying to understand a proof from the paper: Balcázar, José L.; Gavaldà, Ricard; Hermo, Montserrat: Compressiblity of infinite binary sequences, Published in: Complexity, Logic, and Recursion Theory, A. Sorbi, ed., Marcel Dekker 1997, ISBN 0-8247-0026-0, 75-91.

Theorem 19 For every recursive time bound f , there is an infinite sequence that is in $C4[O(1), poly]$ but not $DTIME(f (n))$-computable. (The sequence is automatically in $C5[O(1), poly]$ and in $CK[O(1), poly]$.)

Proof: The main idea is to build a tally set $T\subseteq\{0\}^*$ with the following properties:

• $\chi^T$ is not $DTIME(f (n))$-computable, where $\chi^T$ is the characteristic sequence of $T$ over $\{0\}^*$

• $T \in\ DTIME(g(n))$, for some nondecreasing time-constructible time bound $g$ such that $g(n) \gt f (n)$.

• strings in $T$ are very far one from another; more precisely, $T$ contains only strings of the form $0^{s(m)}$ , where $s$ is defined inductively by: $s(1) = 1;$ $s(m + 1) = g(s(m))$ [...]

(the proof proceeds by using the third property to show that it's easy/polynomial to create $\chi^{T \leq n}$ up to an uncertainty in exactly one hard bit, and so it is possible to consider two machines, one answering $1$ and an other answering $0$ for it, fulfilling the requirement of $\chi^T$ being in $C4[O(1), poly]$ )

This Theorem is claiming to build a tally set that does the job, and I understand how the proof proceeds, once it is taken granted that the set with the specified properties exists, but I don't see its existence proven. How do we know that such a tally set exists for every recursive $f(n)$ that is not $\mathrm{DTIME}(f(n))$ computable as specified in property (1)?

And why do we have to guarantee in property (2) that the $g(n)$ bound is greater or equal to $f(n)$?

Am I missing something basic about tally sets, or sets vs characteristic sequences in general, or some trivial hierarchy theorem?

• ok, i'm beggining to get it, but it would be nice if someone confirmed this. i missed that you don't have to include 1's for all the places determined by the sequence in 3 (that didn't felt like it could produce 'hard bits' at all) but now as far as i can tell, we're free to map any predicate to those places in the characteristic sequence determined by the inductive ladder sequence in (3), say a problem that is by Hartmanis-Stearns complete for $n^3$ that is $g(n) = n^3$ and so if say $n^2 = f(n) \leq g(n)$ it follows trivially that $\chi^T$ is not in $DTIME(n^2)$ – Attila Szasz Jan 24 '15 at 22:32
• Could you try to make your question a little more self-contained? At the moment, it's meaningless without following the link to the proof you're asking about. – David Richerby Jan 24 '15 at 23:07