On checking versus evaluation of multiple queries (Q1260648)

The authors investigate the question, how many queries to an oracle are needed in order to verify a list of answers to \(k\) queries to the same oracle. First they show for the halting set as the oracle that two parallel queries suffice to verify any number of query answers, but one query is not enough. The main result of the first part is Theorem 2.14: In every r.e. Turing degree there is an r.e. set, such that any number of queries can be checked by two parallel queries, but there is also an r.e. set in the same degree, such that checking the answers to \(k\) queries is not possible by less than \(k\) queries. In the last part of the article the problem is transferred to complexity theory. Now the queries of the checking machine are not restricted to the original oracle, but any other oracle from the given complexity class is allowed. The results induce new proofs for conditional collapses, like: the boolean hierarchy over \(NP\) collapses to \(P^{NP[1]}\) if and only if logarithmically many queries to \(NP\) can be replaced by one.