A language L is self-reducible if for every word w, the question "w ∈ L?" can be reduced in polynomial time to questions "q ∈ L?" such that every word q is smaller than w. For example, most NP-complete languages are self-reducible.
A partial information algorithm for a language L computes in polynomial time partial information about the membership of its input words in L. Such algorithms are classified depending on the type of partial information they compute. In the literature, languages with many interesting types of partial information algorithms have been studied extensively, for example p-selective, strongly membership comparable, p-cheatable and easily countable languages.
Buhrman, van Helden, and Torenvliet showed that the languages in P can be characterized as self-reducible p-selective languages. We show that this also holds for languages with other types of partial information algorithms. For example, this holds for easily 2-countable languages and languages which are strongly 2-membership comparable as well as its complement. On the other hand, we discuss whether there are self-reducible languages that are not in P and have partial information algorithms.
} }