Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CHEATABLE:
Reports tagged with cheatable:
TR00-077 | 24th August 2000
Till Tantau

On the Power of Extra Queries to Selective Languages

Revisions: 1

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} ... more >>>




ISSN 1433-8092 | Imprint