A languages 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 different selectivity

classes like the P-selective languages or the semirecursive (i.e.

recursively selective) languages. Generalising a concept introduced by

Beigel et al. we define the selective query complexity of a language

as the minimum number of queries to any selective language needed to

decide it. Our main result shows that the logspace k-truth-table

equivalence closre of every selective, non-cheatable language has

parallel selective query complexity exactly k. We rephrase this

result in terms of the language ODD^N_k = {<w_1,...,w_k> |

\sum_i=1^k \chi_N(w_i) is odd} and obtain the following generalisation

of an important recusrion theoretic result of Beigel et al.:

For selective, non-cheatable sets N the parallel selective query

complexity of ODD^N_k is exactly k. Our proofs are based on a

partial information analysis of the involved languages: We establish

matching uppen and lower bounds for the partial information complexity

of the different equivalence and reduction closures of selective

languages. From this we derive the main results as these bounds differ

for different numbers of queries.

We give four applications of our main theorem and the proof

technique. First, the relations E^P_{k-tt} (P-sel) \not\subseteq

R^P_{(k-1)-tt} (P-sel) and E^P_{tt} (P-sel) \not\subseteq

R^P_{btt} (P-sel) proven by Hemaspaandra et al. still hold if we

relativise only the right hand sides. Second, we settle an open

problem: Equivalence to a P-selective language with k serial queries

cannot generally be replaced by a reduction using less than 2^k-1

parallel queries. Third, the k-truth-table reduction closures of

selectivity classes are (m,n)-verbose iff every walk on the

n-dimensional hypercube with transition counts at most k visits at

most m bitstrings. Lastly, these reduction closure are (m,n)-recursive

iff ever such walk is contained in a closed ball of radius n-m.

A language is \emph{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 different \emph{selectivity classes} like

the P-selective or the semirecursive (i.e. recursively

selective) languages. A language is \emph{supportive} if

$k$ queries to the language are more powerful than

$k-1$ queries for every $k$. Recently, Beigel et al.

(J. of Symb. Logic, 65(1):1--18, 2000) proved a powerful

recursion theoretic theorem: A semirecursive language is

supportive iff 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 \emph{a selective

language is supportive iff 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.

Our proof is based on a partial information analysis

(see Nickelsen, STACS 97, LNCS 1200, pp. 307-318)

of the involved languages: We establish matching

upper and lower bounds for the partial information

complexity of the equivalence and reduction

closures of selective languages. From this we derive

the main results as these bounds differ for

different $k$.

We give four applications of our main theorem and the

proof technique. Firstly, the relation

$E^P_{k-tt}(P[SEL]) \not\subseteq R^P_{(k-1)-tt}(P[SEL])$

proven by Hemaspaandra et al. (Theor. Comput. Sci.,

155(2):447-457, 1996) still holds, \emph{if we relativise

only the right hand side}. Secondly, we settle an open

problem from the same paper: Equivalence to a P-selective

language with $k$ \emph{serial} queries cannot

generally be replaced by a reduction using less than

$2^k-1$ \emph{parallel} queries. Thirdly, the

$k$-truth-table reduction closures of selectivity classes

are $(m,n)$-verbose iff every walk on the $n$-dimensional

hypercube with transition counts at most $k$ visits

at most $m$ bitstrings. Lastly, these reduction closures

are $(m,n)$-recursive iff every such walk is contained

in a closed ball of radius $n-m$.