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 6.6 (page 188): verify that P and EXP are closed under
polynomial-time reductions, but that E need not be.
Retrieve the Postscript file or the
HTML file.
Exercise 6.11 (page 213): verify that logspace reductions are transitive.
Retrieve the Postscript file or the
HTML file.
Exercise 6.19, second half (page 220): verify that every set in NP is
the range of an honest polynomially computable function.
Retrieve the Postscript file or the
HTML file.
Exercise 6.28 (page 222): verify that NP is closed under conjunctive
polynomial-time reductions.
Retrieve the Postscript file or the
HTML file.
