 |
The Theory of Computation | Bernard M.E. Moret |
|
SOLUTION MANUAL: CHAPTER 8
Solutions are given here to nearly all of the exercises in Chapter 8 of the text
as well as to most of the additional problems for that chapter.
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. 287) k,2-SAT is in P for each k
- Exercise 2 (p. 296) Planar NAE3SAT is in P
- Exercise 3 (p. 299) promises that cross the decidability or tractability barrier
- Exercise 4 (p. 309) similarity between (N)P and (N)PO
- Exercise 5 (p. 327) properties of PTAS reductions
- Exercise 6 (p. 334) approximation classes and P?NP
- Exercise 7 (p. 340) instance-dependent parameter and RP vs. NP
-
in the exercise section
- Exercise 8 Planar 3SAT is NP-complete
- Exercise 9 Planar 1in3SAT is NP-complete
- Exercise 10 VC and MxC remain NP-complete for graphs of degree 3
- Exercise 11 Planar MxC is in P
- Exercise 12 Minimal Research Program is NP-complete
- Exercise 13 uniqueness of solution is harder for some
- Exercise 14 Vizing's theorem
- Exercise 15 Matrix Cover is strongly NP-complete
- Exercise 16 Memory Management is strongly NP-complete
- Exercise 17 Safe Deposit Boxes is NP-complete
- Exercise 18 approximation algorithm for Safe Deposit Boxes
- Exercise 19 approximation algorithm for Minimum-Degree Spanning Tree
- Exercise 20 constant-distance approximation is NP-hard for some simple problems
- Exercise 21 constant-distance approximation is NP-hard for some harder problems
- Exercise 22 sublinear distance approximation
- Exercise 23 0.5 approximation for VC
- Exercise 24 0.5 approximation for MxC
- Exercise 25 PTAS for Knapsack through completion
- Exercise 26 Product Knapsack is in FPTAS
- Exercise 27 sufficient conditions for membership in FPTAS
- Exercise 28 simplicity and pseudo-polynomial time
- Exercise 29 approximation through shifting for graphs
- Exercise 30 simplicity and boundedness
- Exercise 31 MaxWSAT is PTAS-hard for NPO
- Exercise 32 MxC is OptNP-complete
- Exercise 33 MaxBoundedWSAT is Apx-complete
- Exercise 34 BPP can be defined with very small constants
- Exercise 35 a priori probability, PP, and low levels of PH
- Exercise 36 #P and PP are very similar
- Exercise 37 define PPSPACE and prove PPSPACE=PSPACE
- Exercise 38 P-bi-immunity and special-case solutions
- Exercise 39 RP and BPP are semantic classes
Additional Exercises