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.