[35] Let L = 12 ... be the characteristic sequence for language L {0, 1} such that i = 1 iff the lexicographically ith

[35] Let χL = χ1χ2 ... be the characteristic sequence for language L ⊆ {0, 1}∗ such that χi = 1 iff the lexicographically ith word wi is in L. As before, L

. Prove by diagonalization:

(a) There is language L ∈ DTIME[22O(n)

] which is such that the t(n)

time-bounded Kolmogorov complexity of L is exponential almost everywhere (note: χL s(n, ), for some c > 1,> 0.

(b) Use Item

(a) to show that if L is DTIME[22O(n)

]-hard under polynomial-time Turing reduction, then the t(n) time-bounded Kolmogorov complexity of L is exponential almost everywhere. That is, for all but finitely many n, Ct(n),∞(χL s(n, ), for some c > 1,> 0.

(c) There is a language L ∈ SPACE[2O(n)] such that for all but finitely many n, we have C∞,2n

(χL 2n−2.

(d) Use Item

(c) to show that if L is SPACE[2O(n)]-hard under polynomialtime Turing reduction, then there exists a constant  > 0 such that for all but finitely many n, we have C∞,s(n,)

(χL s(n, ).

(e) There is a language L ∈ SPACE[2O(n)

] such that for large enough n, C∞,2n

(χL 2n − n.

(f) Consider the P/poly class defined in Exercise 7.2.6.

It is not known whether DTIME[t(n)] is contained in P/poly. A nonsparse language L is said to be P/poly immune if it has only sparse subsets in P/poly. A language L is said to be P/poly bi-immune if L and its complement are both P/poly immune. Use Item

(e) and the language L in that item to show that there exists a language L ∈ SPACE[2O(n)

] that is P/poly bi-immune.

Comments. Source: D.T. Huynh in [Proc. 1st Conf. Structure Complexity Theory, 1986, pp. 184–195; Theoret. Comput. Sci., 96(1992), 305–324;

Inform. Comput., 90(1991), 67–85; Inform. Process. Lett., 37(1991), 165–

169].