2013 June 3,

CS 254: Day 26

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.