Solutions (or Hints) to Chapter-end Exercises J!O! 415
if: Let P be IVP-complete and P E NP. Let L be any language in NP.
We get a polynomial reduction ¢ of L to P and hence a polynomial
reduction If! of [ to p. We prove NP c CO-NP. Combine If! and
nondeterministic polynomial-time algorithms for p to get a
nondeterministic polynomial-time algorithm for [. So [ E NP or L
E CO-NP. This proves NP c CO-NP. The other inclusion is similar.