picture of text cover

The Theory of Computation

Bernard M.E. Moret



ADDITIONAL EXERCISES FOR CHAPTER 7


NP-Completeness Proofs

These problems can all be shown complete through very simple reductions from one of the standard NP-complete problems in the text (mostly from some variety of 3SAT or HC).

Other Completeness Proofs



Other Problems



Back to The Theory of Computation