  Can easy sets only have easy certificate schemes? In this paper, we study the
class of sets that, for all NP certificate schemes (i.e., NP machines), always
have easy acceptance certificates (i.e., accepting paths) that can be computed
in polynomial time. We also study the class of sets that, for all NP
certificate schemes, infinitely often have easy acceptance certificates.
  In particular, we provide equivalent characterizations of these classes in
terms of relative generalized Kolmogorov complexity, showing that they are
robust. We also provide structural conditions---regarding immunity and class
collapses---that put upper and lower bounds on the sizes of these two classes.
Finally, we provide negative results showing that some of our positive claims
are optimal with regard to being relativizable. Our negative results are proven
using a novel observation: we show that the classical ``wide spacing'' oracle
construction technique yields instant non-bi-immunity results. Furthermore, we
establish a result that improves upon Baker, Gill, and Solovay's classical
result that NP \neq P = NP \cap coNP holds in some relativized world.
