|
|
|
|
|
|
An oracle scientist M in the process of OAEx-identifying a function f may ask infinitely many questions of the oracle A. A natural refinement on the OAEx paradigm is to bound the number of questions a scientist is allowed to ask. This refinement is the subject of the next definition. First, we formalize the concept of ''set of questions asked of an oracle by a scientist examining the graph of a function." |
|
|
|
|
|
|
|
|
Let Queries(M, A, s ) denote the set { asks a question of the form  of A in conjecturing a hypothesis on c }. Then the set of queries to A by M on a function f, denoted Queries(M, A, f), is  Queries(M,A,f[n]). |
|
|
|
|
|
|
|
|
11.10 Definition (Gasarch and Pleszkoch [76]) Suppose  and M is an oracle scientist. |
|
|
|
|
|
|
|
|
(a) M OA,bEx-identifies f (written:  ) just in case  and  . |
|
|
|
|
|
|
|
|
(b)  . |
|
|
|
|
|
|
|
|
Intuitively, an oracle scientist M is said to OA,bEx-identify a function f if and only if M OAEx-identifies f by asking only up to b distinct queries of A. As an immediate corollary of Lemma 11.8 we have |
|
|
|
|
|
|
|
|
11.11 Corollary If  , then OA,*Ex = Ex. |
|
|
|
|
|
|
|
|
Fortnow, Gasarch, Jain, et al. [59] show the converse to this. |
|
|
|
|
|
|
|
|
A natural question is whether there is anything to gain from allowing oracle scientists to ask additional queries. The next proposition shows that this is indeed the case—provided the oracle involved is powerful enough. |
|
|
|
|
|
|
|
|
11.12 Proposition (Fortnow, Gasarch, Jain, et al. [59]) For all A, the following are equivalent. |
|
|
|
|
|
|
|
|
(a)  |
|
|
|
|
|
|
|
|
(b) For all n,  |
|
|
|
|
