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$.