The Theory of Computation

Because most of these solutions require a fair amount of notation, the first version of this solution manual provides only Postscript files. In the near future, an HTML version should be available, but it will require Netscape with some modifications in order to be readable, since mathematics support remains minimal under HTML.

Exercises from the text are referred to by their number; additional exercises use numbers matching those given in the list of additional exercises. For convenience, each entry below also gives a few keywords for each exercise to help in locating a specific exercise.

Files use plain fonts (Computer Modern) and formatting rather than the fonts and format of the text and so are small for fast downloading.

Text Exercises

• within the text
  • Exercise 1 (p. 173) reduce X2C to matching
  • Exercise 2 (p. 173) reduce Partition to Kth Largest Subset
  • Exercise 3 (p. 175) transitivity of reductions
  • Exercise 4 (p. 177) completeness implies equivalence, but not the reverse
  • Exercise 5 (p. 181) space constructible is fully space constructible if large enough
  • Exercise 6 (p. 188) P and EXP are closed under poly-time reductions, E is not
  • Exercise 7 (p. 191) PolyL is closed under log-space reductions
  • Exercise 8 (p. 194) NP is closed under poly-time reductions
  • Exercise 9 (p. 201) how to place a problem within a hierarchy
  • Exercise 10 (p. 212) where do the arbitrary quantifiers of QBF come from?
  • Exercise 11 (p. 213) log-space reductions are transitive
  • Exercise 12 (p. 217) why can we not reason about P as we do about PolyL?
  • Exercise 13 (p. 217) hardness and intractability
  • Exercise 14 (p. 217) EXP and EXPSpace contain intractable problems
• in the exercise section
  • Exercise 15 some basic time- and space-constructible functions
  • Exercise 16 proof of translational lemma
  • Exercise 17 nondeterministic space hierarchy
  • Exercise 18 prove that P is distinct from linear space
  • Exercise 19 honest functions and NP
  • Exercise 20 P=NP implies EXP=NEXP
  • Exercise 21 SAT is log-space complete for NP
  • Exercise 22 what is some NP-complete problem is not log-space complete for NP?
  • Exercise 23 solve Digraph Reachability in $log2n$ space
  • Exercise 24 subexponential time
  • Exercise 25 syntactic classes of complexity
  • Exercise 26 flawed proofs for settling P?NP
  • Exercise 27 Turing vs. many-one reductions within NP
  • Exercise 28 NP is closed under conjunctive poly-time reductions

Additional Exercises

• Additional Exercise 1 closure of P and NP under union and intersection
• proof of Theorem 6.1 (no space class between constant and Theta(loglog n) )
• Additional Exercise 3 constant space is exactly the regular languages