Natural Self-Reducible Sets
Alan L. Selman · SIAM Journal on Computing · 1988
To every set A in NP we associate a (collection of) natural self-reducible set${\operatorname{set}}(s)$. We prove that every disjunctive-self-reducible set in NP is $ \leqq _d^P $-equivalent to one of these natural self-reducible sets and we show that if certain questions about these sets could be answered, then several significant open questions about the fine structure of NP would be solved.