The Theory of Computation
Bernard M.E. Moret
ADDITIONAL EXERCISES FOR CHAPTER 6
Additional Exercise 1
Prove that both P and NP are closed under union and intersection.
Additional Exercise 2
Verify that, if a Turing machine uses o(loglog n) space, then it uses only constant space -- this is the proof of Theorem 6.1.
Additional Exercise 3
(hard) Prove that SPACE(O(1)) is exactly the class of regular languages.
Back to
The Theory of Computation
