Easy Sets and Hard Certificate Schemes

Details Easy Sets and Hard Certificate Schemes Easy Sets and Hard Certificate Schemes

1999-07-25

arxiv.org/abs/cs/9907035v1

Acta Informatica vol. 34, no 11, pp. 859--879, 1997

Computer Science

Computational Complexity

26 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Easy Sets and Hard Certificate Schemes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Easy Sets and Hard Certificate Schemes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Easy Sets and Hard Certificate Schemes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-619290