Yenjo Han and Thomas Thierauf
Abstract:
We investigate classes of sets that can be
decided by bounded truth-table reductions to an NP set in which
evaluators do not have full access to the answers to the queries
but get only restricted information
such as the number of queries that are in the oracle set
or even just this number modulo m, for some m > 1.
We also investigate the case in which evaluators are nondeterministic.
We show that when we vary the information that the evaluators get,
this can change the resulting power of the evaluators.
We locate all these classes within levels of the Boolean hierarchy
which allows us to compare the complexity of such classes.