[44] Show that simulating a linear-time 2-tape deterministic Turing machine with one-way input by a 1-tape nondeterministic Turing machine with one-way input requires (n2/((log n)2

[44] Show that simulating a linear-time 2-tape deterministic Turing machine with one-way input by a 1-tape nondeterministic Turing machine with one-way input requires Ω(n2/((log n)2 log log n)) time.

Comments. Hint: Let S be a sequence of numbers from {0,...,k − 1}, where k = 2l for some l. Assume that each number b ∈ {0,...,k − 1} is somewhere in S adjacent to the number 2b (mod k) and 2b+ 1 (mod k).

Then for every partition of {0,...,k − 1} into two sets G and R such that d(G), d(R) > k/4 there are at least k/(c log k) (for some fixed c)

elements of G that occur somewhere in S adjacent to a number from R. Subsequently prove the lower bound using the language L ⊆ {0, 1}∗

defined as follows. Let u = u1 ...uk, where the ui’s are of equal length.

Form uu = u1 ...u2k with uk+i = ui. Then inserting ui between u2i−1 and u2i for 1 ≤ i ≤ k results in a member in L. These are the only members of L. Source: [W. Maass, Trans. Amer. Math. Soc., 292(1985), 675–693]. The language L defined in this hint will not allow us to obtain an Ω(n2) lower bound. Define a graph G = Zn, Eab , where Zn =

{0, 1,...,n − 1}, Eab = {(i, j) : j ≡ (ai +

b) mod n for i ∈ Zn}, and a and b are fixed positive integers. Then G has a separator, a set of nodes whose removal separates G into two disconnected, roughly equal-sized components of size O(n/loga n). Using such a separator, L can be accepted in subquadratic time by a 1-tape online deterministic machine

[M. Li, J. Comput. System Sci., 7:1(1988), 101–116].