期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2000
卷号：2000
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 = { |
\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.
