2013 June 3,

Carleton College, Spring 2013

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

A. Define EXPSPACE and NEXPSPACE, and prove that EXPSPACE = NEXPSPACE. (This problem is not very large or difficult, but I'm looking for a rigorous argument, that uses your defined concepts correctly.)

B. Problem 8.4.

C. Problem 8.17. (You have to read the definition of the complexity class L in the textbook. It's not hard to understand, but there is some subtlety in how sub-linear space is measured.)

Do not do Problem D. It is not part of this assignment. I'm leaving it here in case you find it helpful as a study question.

D. For any positive integers *n* and *b*, let <*n*>_{b} denote the base-*b* numeral for *n* (with no leading zeros). Consider a Turing machine *F* that takes strings <*n*>_{2} as input, and outputs the corresponding strings <*n*>_{1}. For example, when given input 101, *F* halts with its tape containing 11111 and nothing else. I've left out the details of how *F* is implemented. Explain how *F* could be implemented to operate in exponential time and exponential space. Prove that *F* cannot be implemented to operate in polynomial time or polynomial space. Finally, explain why this example does NOT prove that P ≠ EXPTIME or PSPACE ≠ EXPSPACE.