2013 May 15,

Carleton College, Spring 2013

Prof. Joshua R. Davis, , CMC 325, x4473

A. Let *f*(*n*) be a function that limits to infinity as *n* goes to infinity. Prove that O(2^{f(n)}) is a proper subset of 2^{O(f(n))}.

When we were studying computability, we showed that a *k*-tape Turing machine is equivalent to a single-tape Turing machine. We actually made two or three arguments for this fact. One argument worked by interleaving the *k* tapes on the single tape. Another argument worked by enlarging the tape alphabet to consist of *k*-tuples of tape symbols. Now that we're studying complexity, we've shown that the interleaving approach leads to (at worst) a quadratic blowup in running time.

B. Does the *k*-tuple approach also lead to a quadratic blowup in running time?