On the Power of Extra Queries to Selective Languages
Till Tantau · 2000
A language is selective if there exists a selection algorithm for it. Such an algorithm selects from any two words one, which is an element of the language whenever at least one of them is. Restricting the complexity of selection algorithms yields dierent selectivity classes like the P-selective or the semirecursive (i. e. recursively selective) languages. A language is supportive if k queries to the language are more powerful than k 1 queries for every k. Recently, Beigel et al. [4] proved a powerful recursion theoretic theorem: A semirecursive language is supportive i it is nonrecursive. For restricted computational models like polynomial time this theorem does not hold in this form. Our main result states that for any reasonable computational model a selective language is supportive i it is not cheatable. Beigel et al.'s result is a corollary of this general theorem since `recursively cheatable' languages are recursive by Beigel's Nonspeedup Theorem [2]. Our proof is based on ...