# The Theory of Computation

## SELECTED SOLUTIONS FOR CHAPTER 7

We recommend downloading and viewing or printing the Postscript files, due to their much better presentation. Postscript files follow the style of the text (fonts, sizes, notation, etc.), whereas HTML files use whatever tools are at hand to render the mathematical formulae.
• Exercise 7.1, part 2 (page 232): prove that Positive NAE3SAT is NP-complete. Retrieve the Postscript file or the HTML file.
• Exercise 7.11 (page 268): prove that Minimal Unsatisfiability is NP-complete when we do not care whether the instance is itself satisfiable. Retrieve the Postscript file or the HTML file.
• Exercise 7.27, part 3 (page 278): prove that Maximum-Leaves Spanning Tree is NP-complete. Retrieve the Postscript file or the HTML file.
• Exercise 7.39 (page 280): prove that Two-Unsatisfiability is NL-complete. Retrieve the Postscript file or the HTML file.
• Exercise 7.45 (page 281): prove that Unique Satisfiability cannot be in NP unless we have NP=coNP. Retrieve the Postscript file or the HTML file.
• Exercise 7.55 (page 283): prove that a tally language cannot be NP-complete unless we have P=NP. Retrieve the Postscript file or the HTML file.

 Back to The Theory of Computation