EASY SETS AND HARD CERTIFICATE SCHEMES

Can easy sets only have easy certificate schemes? In this paper, we st udy the class of sets that, for all NP certificate schemes (i,e., NP m achines), always have easy acceptance certificates (i.e., accepting pa ths) that can be computed in polynomial time. We also study the class of sets that, for all NP certificate schemes, infinitely often have ea sy acceptance certificates. In particular, we provide equivalent chara cterizations of these classes in terms of relative generalized Kolmogo rov complexity, showing that they are robust. We also provide structur al conditions-regarding immunity and class collapses-that put upper an d 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 us ing a novel observation: We show that the classical ''wide spacing'' o racle construction technique yields instant non-biimmunity results. Fu rthermore, we establish a result that improves upon Baker, Gill, and S olovay's classical result that NP not equal P = NP boolean AND coNP ho lds in some relativized world.