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.
