# 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)$ Jan 24, 2015 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. Jan 24, 2015 at 23:07