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.
展开▼
