 |
The Theory of Computation | Bernard M.E. Moret |
|
SOLUTION MANUAL: CHAPTER 9
Solutions are given here to nearly all of the exercises in Chapter 9 of the text.
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.
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. 364) proof that the instance complexity
of a problem is always bounded by its descriptional complexity
- Exercise 2 (p. 365) proof that P is exactly the
set of problems that have instances of constant instance complexity.
- Exercise 3 (p. 366) proof that problems not in P must
have an infinite number of hard instances
- Exercise 4 (p. 367) proof that at most a finite number of hard instance can be mapped onto a single instance in any polynomial transformation
- Exercise 5 (p. 371) proof that AP is closed under
polynomial-time reductions defined for distrbutional problems
- Exercise 6 (p. 378) should uniformity (for circuit-based definitions) be sepcified on both bounds or on one bound only?
- Exercise 7 (p. 380) proof that Digraph Reachability is in NC
- Exercise 8 (p. 389) proof that IP is a subset of PSPACE
- Exercise 9 (p. 389) some properties of partial-sum polynomials used in the IP protocol for 3UNSAT
- Exercise 10 (p. 390) proof that 3UNSAT belongs to IP
- Exercise 11 (p. 395) what is the class PCP(0,q)