UNIVERSITY OF 
 
 ILLINOIS LIBRARY 
 
 AT URBANA-CHAMPAJ6N 
 
The person chareing- this mo* 
 
 sponsible for its ret?,? 7 , mater »al >s re- 
 which it was withdr, ° thG librar ^ from 
 
 the Universify. m ° y reso " i" dismi sso | from 
 
 To renew coll Telephone Center 333 »* nn 
 
 L161— O-1096 
 
Digitized by the Internet Archive 
 in 2013 
 
 http://archive.org/details/restrictedoracle995plai 
 
UIUCDCS-R- 79-995 
 
 UILU-ENG 79 1743 
 
 October 1979 
 
 Restricted Oracles 
 
 by 
 David A. Plaisted 
 
 * • 
 
 1 
 
 DEPARTMENT OF COMPUTER SCIENCE 
 UNIVERSITY OF ILLINOIS AT URBANA-CHAMPAIGN 
 
 URBANA, ILLINOIS 
 
 IHE LIBRARY OF THE 
 
 MAY y i960 
 
 UNIVERSITY OF ILLINOIS 
 ''RRANA-CHAMPAIGN 
 
Restricted Oracles* 
 
 by 
 
 David A. Plaisted 
 
 University of Illinois at Urbana-Champaign 
 Urbana, Illinois 61801 
 
 * This research was partially supported by the National Science Foundation 
 under grant MCS 77-22830. 
 

 Abstract 
 
 An oracle for a Turing machine is restricted if the amount 
 of oracle that may be examined on inputs of a given size is restricted 
 in various ways. This concept yields interesting hierarchies for solvable 
 as well as for unsolvable problems. One of these hierarchies is used to 
 get lower bounds on the sizes of the axioms needed to decide the halting 
 problem of a Turing machine on larger and larger inputs. The combinational 
 complexity of initial portions of a binary language is related to the 
 amount of oracle necessary to recognize the language. Complete problems 
 for PSPACE, NP, P, and NLOGSPACE relative to arbitrary restricted and 
 unrestricted oracles are presented. Every binary language has a 
 "compressibility", a restriction on oracles which is about as tight 
 as possible while still allowing the language to be accepted. The 
 compressibility of a language is a measure of the complexity of the 
 language which is an alternative to Kolmogorov complexity for finite 
 sequences and to program complexity for finite functions. 
 
-1- 
 
 1. Introduction 
 
 We consider Turing machines with oracles, in which the use 
 of the oracle is restricted. In particular, the magnitude of a query 
 that may be given to the oracle is bounded by a function of the magnitude 
 of the input. This function is called the utilization of the oracle. 
 Restricted oracles were studied in [8]. We show that there are arbitrarily 
 hard languages accepted in polynomial time relative to \/ery slowly 
 utilized oracles, and comparatively easy languages that are not. We 
 give several hierarchy results for restricted oracles, based on diagonalization 
 arguments. Using one of the hierarchy results, we derive a lower bound 
 for the amount of oracle needed to solve one version of the halting 
 problem. From this result, we get a lower bound on the sizes of the 
 axioms needed to decide halting problems for larger and larger inputs 
 to a Turing machine, in any reasonable logical theory. We exhibit a 
 trivial sub-linear upper bound on the amount of oracle needed to solve 
 another version of the halting problem. Also, we show that for many 
 utilizations f, the probability is zero that an arbitrary binary language 
 can be accepted relative to an f(x) - utilized oracle. We present a 
 conjecture which extends this result, but which we cannot prove. Several 
 relationships with Boolean circuit complexity are then explored. We 
 show that it is undecidable whether a Turing machine in EXPSPACE accepts 
 a language which can be accepted in polynomial time relative to a "slowly 
 utilized oracle". However, if such an oracle exists, it can be found in 
 polynomial space. We show that P f NP iff there exists a slowly utilized 
 oracle A relative to which P f NP, and all problems in NP have small circuits 
 iff there exists a slowly utilized oracle relative to which P = NP. Thus 
 
-2- 
 
 restricted oracles have quite different complexity theoretic properties 
 
 from unrestricted oracles. We exhibit complete problems for various 
 
 complexity classes relative to arbitrary restricted and unrestricted 
 
 oracles. Also, we ask how slowly utilized an oracle can be and still be 
 sufficient to accept a language. It turns out that there are oracles 
 
 which are utilized about as little as possible among all oracles for a 
 
 language. 
 
 Next we explore relationships of slowly utilized oracles to 
 slowly growing sets of inference rules and increasingly more powerful 
 decision procedures. We can capture the intuitive idea that finite 
 initial portions of a language may not be too difficult, even if the 
 language as a whole is undecidable. Thus, with a slowly growing table of 
 knowledge, we may be able to obtain better and better problem solving 
 methods in various logical theories. Finally, we explore relationships 
 of restricted oracles to random computations, random number generators, 
 and the P=PSPACE question. 
 
 The model of Turing machines we will use has a read-only input 
 tape and a working tape. The input is in binary. Also, the Turing machine 
 has a binary oracle A which works as follows: Whenever the Turing machine 
 enters one of possibly many "oracle states" q, the binary string immediately 
 to the right of the working tape head is used as the input to the oracle. 
 The right boundary of this string is indicated by any non-binary character. 
 If this binary string is x, and x e A, then the Turing machine enters 
 some state q,. If x I A, the Turing machine enters some other state qg. 
 For each q, their may be different q n and q-, . None of the contents of 
 the tapes are changed. The oracle A may be viewed as a binary language. 
 
-3- 
 
 We define the utilization of an oracle by a Turing machine in 
 terms of an ordering on binary strings. We use a particular total ordering 
 in the following discussion, but it would be interesting to see how these 
 concepts generalize to other partial orderings. Let |x| denote the 
 length of a binary string x. We order binary strings lexicographically. 
 That is, x < y if |x| < |y| or if |x| = |y| and x = uOv and y = ulw for 
 some strings u, v, w. We define index(x) to be the number of binary 
 strings y such that y <_ x. Thus index(e) = 1, index(O) = 2, index(l) = 3, 
 index(OO) = 4 et cetera. (Here e is the empty string, signifying a blank 
 tape.) Note that index(x) is the binary number obtained by prefixing x 
 with a one. A utilization is a function f mapping binary strings to 
 nonnegative integers such that f(x) <_ index(x) for all x and such that 
 x < y implies f(x) <_ f(y). 
 
 Definition . Suppose Turing machine T has a binary oracle A. 
 Then A is f (x)-utilized if f is a utilization and if on input x to T, 
 the oracle A is never queried on strings y with index(y) > f(x). Thus the 
 number of different queries that may be given to the oracle on inputs 
 {x: index(x) £ n} is bounded by f(n). For example, if f(x) is |_index(x)/2j 
 and x = 000 then the only permissible queries to the oracle would be 
 1, 2, 3, and 4. Note that if f(x) = for all x then no queries may be given 
 to the oracle at any time. We constructed the definitions to allow for 
 this possibility. The intuition for this definition is that the number 
 of distinct queries that may be given to the oracle is bounded by a function 
 of the "size" of the input to T. We assume that the input tape of T is 
 blank except for the binary input. The index function was constructed to 
 distinguish inputs having different numbers of leading zeroes. 
 
 We identify the oracle A with the infinite binary string A(1)A(2)A(3) 
 where A(index(x)) =1 if x e A and A(index(x)) = otherwise. 
 
-4- 
 
 Definition : We write n to indicate the unique binary string 
 x such that index(x) = n. Also, we frequently identify a binary string x 
 with the integer index(x). Note that this is a nonstandard mapping of 
 binary strings to integers. Thus we may write A(j) instead of A(j). 
 
 In the following discussion, we assume that R is a deterministic 
 or nondeterministic time or tape complexity class. That is, R is of 
 the form DTIME(g(x)), NDTIME(g(x) ) , DTAPE(g(x)), or NDTAPE(g(x) ) . 
 In tape complexity classes, we consider the amount of the working tape 
 used. Also, R may be a union of complexity classes of this form. Thus 
 R may be P, NP, PSPACE, et cetera. Also, we use "Recursive" to denote 
 the set of recursive languages and "RE" to denote the set of recursively 
 enumerable languages. We often use PTIME instead of P. 
 
 Definition : Suppose R is a complexity class for Turing machines, 
 f is a function from binary strings to natural numbers, and A is a binary 
 oracle. Then C Q (R, f, A) is the set of binary languages accepted by some 
 Turing machine T in complexity class R with f (x)-utilized oracle A. 
 
 Definition : C Q (R, f) = VC (R, f> A). Here the union is taken 
 over all binary oracles. Note that if f is a utilization then we can consider 
 C (RE, f), the set of languages accepted by a Turing machine T relative to 
 an f (x)-utilized oracle, such that T need not halt on all inputs. Also, 
 eyery binary language is in C (R, f) if f(x) = index(x) and R is linear 
 time. We will show that this is not true for most smaller functions f. 
 Since RE c C (RE, f) for all utilizations f, C Q (RE, f) can only be used 
 to get hierarchies of unsolvable (not partially solvable) problems. However, 
 C (R, f) for other complexity classes R can be used to obtain hierarchies 
 of solvable problems. 
 
-o- 
 
 We could also define Cg(R, f, A) to include only languages that are 
 many-one reducible to A by a Turing machine in complexity class R. Some of the 
 results (including Theorems 1, 2.1, 2.2, 2.3, 2.4, 2.5, 2.8, 2.9, 2.10, 2.11, 2.12, 
 3.2, 6.2, and maybe more) still hold for this definition. 
 
 Definition : If L e c q( r > f ^ then we say L can be acce P ted 
 in class R relative to an f (x)-utilized oracle. 
 
 Definition : If f(x) is asymptotically bounded by log(index(x)) k 
 for some k, then we say an f(x) -utilized oracle is a slowly utilized oracle . 
 
 Definition : C Q (R, slow, A) = k u Q C (R, log(index(x)) k , A) and 
 C Q (R, slow) = k ^ C (R, log(index(x)) k ). 
 
 If L is sparse, then L E C Q (PTIME, slow). Also, L e C q (R, f) iff 
 
 the complement of L is in C Q (R, f ) . 
 
 If f is bounded, then a Turing machine can encode the appropriate 
 
 portion of an oracle in its states. Also, sufficiently many working 
 
 tape squares to the right of the working tape head can be kept in a finite 
 
 control. For example, if f(x) <_ d then about logd tape squares need to be 
 
 kept in the finite control. Then C Q (DTIME(g(x) ) ,f ) c DTIME(g(x)). Also, 
 
 C Q (DTAPE(g(x)), f) c DTAPE(g(x)). In fact, C Q (R, f) c R for all complexity 
 
 classes R considered here if f is bounded. 
 
 Theorem 1 : Suppose f is unbounded and computable in DTIME(g(x)). 
 
 Suppose \/n >_ l3xf(x) = n. Thus there is a computable function h such that 
 
 f(h(n)) = n for all n^l.Then C Q (DTIME(g(x) + 1), f) contains languages at all levels 
 
 of the recursive hierarchy. The constant 1 reflects the time needed to 
 
 query the oracle once. 
 
 Proof : Let A be an arbitrary oracle, and let A(x) be the value of 
 
 A for query x. We are assuming that f(x) is computed on the working tape, 
 
 with the working tape head at the left end of the representation of f(x) 
 
-6- 
 
 when the computation of f ends. Let L be {x: f(x) e A}. Then L e 
 C n (DTIME(g(x) + 1), f). Also, L and A are related by recursive reductions. 
 Thus there can be arbitrarily hard languages in C n (R, f) for slowly growing 
 f and suitable R. For example, there are arbitrarily hard sets in 
 C Q (PTIME, f) where f(x) = Llog 2 (index(x) ) J. 
 
 Note that if A, f, and R are all "easy" then so is C Q (R, f, A) 
 since we can compute the value of A(x) when needed. For example, 
 C (PTIME, f, A) = PTIME if A and f are computable in polynomial time. 
 We showed above that if A is hard, then C ft (R, f, A) has hard sets, for 
 suitable R and f. 
 
 2. Hierarchies of Languages 
 
 We now, show that there are particular oracles which give a 
 
 wery fine hierarchy of languages, by restricting the utilization in different 
 
 ways. Note that the usual time and tape hierarchy results [4 ] apply 
 
 h 2 (x) 
 to a fixed oracle with a fixed utilization. For example, if lim sup . # \ = 0, 
 
 then C Q (DTAPE(h 2 (x)), f, A) is a proper subset of C Q (DTAPE(h 1 (x)) , f, A) 
 
 for all f and A. 
 
 Theorem 2.1 : Suppose f 2 is a utilization function which is 
 
 computable in polynomial time. Suppose there exists a computable function 
 
 g such that for all n >_1, f 2 (g(n)) = n. (That is, suppose (yn >_ l)(3x)f(x) = n.) 
 
 Let A be any oracle which is not recursive. (That is, A(x) is not 
 
 computable as a function of x. ) Then there exists a language 
 
 L e Cq(PTIME, f 2 , A) - C (Recursive, f 2 ~l , A). Thus L can be accepted in 
 
 polynomial time if A is f ? (x) utilized, but L cannot be accepted at all if A 
 
 is f 2 (x)-l utilized. 
 
-7- 
 
 Proof : Let L be {x: f (x) e A}. It is clear that L e C Q (PTIME, f 2> A) 
 We claim that L I C Q (Recursive, f« - 1 , A) . We show that if L e 
 C Q (Recursive, f« - 1 , A) then A is recursive; in particular, for all n, 
 A(n) can be computed from A(n-l), A(n-2), . .., A(l). 
 
 Let Tp be a Turing machine accepting L relative to the f 2 (x) - 1 
 utilized oracle A. Then T 2 accepts g(n) iff f«(g(n)) e A, i.e., iff 
 n e A. However, in its computation, T ? only uses A(l), A(2), ..., 
 A(f 2 (g(n)) - 1), that is, A(l), A(2), ..., A(n-l). Hence if T 2 exists, 
 A(n) is computable from A(l), A(2), ..., A(n-l). 
 
 The following result shows that restricted oracles as a whole 
 give an extremely fine hierarchy of functions. In particular, there are 
 languages accepted in polynomial time relative to an f (x)-utilized 
 oracle, which cannot be accepted at all relative to any oracle utilized 
 slightly less than f(x). 
 
 Theorem 2.2 : Suppose f 2 is a utilization which is computable in 
 polynomial time. Suppose f 2 (x) - f-,(x) is unbounded. Also suppose that 
 (Vn > l)(3x)f 2 (x) = n. Then there is a language L e C Q (PTIME, f 2 ) such that 
 L t C Q (RE, f^. 
 
 Proof : We "construct" an oracle A and a language L such that 
 L e C Q (PTIME, f 2> A) but for no^ oracle B is L e C Q (RE, f ] , B). The 
 language L is {x: f ? (x) e A}. Let T be a Turing machine accepting L in 
 polynomial time relative to the f 2 (x)-utilized oracle A. The argument 
 is a combination of diagonal ization and a counting argument. Let a~, a,, 
 a 2 , ... be an infinite monotone increasing sequence of integers such 
 that for all i >_ 0, foU^-i) - ^i^i+i) > ^o^\)- Also, suppose that 
 f 2 (a Q ) - f , (a Q ) > . Such a sequence must exist because f 2 (x) - f-,(x) 
 is unbounded. Let T fi , T, , T ? , ... be an enumeration of the Turing 
 
-8- 
 
 machines which use f, (x)-utilized oracles. We construct A as an infinite 
 binary string aQd-|a 2 ... where |a. | = f 2 (a.) - fp^i-l^ and ' a o' = ^2^0^' 
 That is, A(j) is the j bit in the string a Q a,a 2 ... . The string a. 
 is chosen so that T. cannot accept L relative to any f, (x)-utilized oracle. 
 The Turing machines T. may reject x by halting and rejecting or by looping. 
 We do not distinguish between these possibilities here. We construct 
 A so that no T. is equivalent to T, even if T. loops on some inputs. 
 
 Let us consider the behavior of T and T- on inputs x such that 
 f 2 (a 1 ._ 1 ) < f 2 (x) < f 2 (Ij), for i > 1. Now, index(x) <a. since f« is 
 
 monotone. Hence T. will only be allowed to use the first f, (a.) bits of 
 
 f l (a V ] 
 
 its oracle. Thus there are 2 possibilities for these bits of 
 
 the oracle for T^ However, oracle A has at least f 2 (a.) - f 2 (a._,) bits 
 
 in a. which can be selected to eliminate T.. Since f (i.) - f-.(a.) > 
 
 f 2^-j--|)» we nave f 2^i) " f 2^i-l^ > VV" Each bit of a i is selected 
 to eliminate at least half of the possibilities for the first f-,(a.) bits 
 of the oracle for T^ With f 2 (a\) - ^(a^-,) bits, we can eliminate 
 all the possibilities for oracles for T- since f 2 (a..) - f ? (a. ,) > 
 
 f^(a"f). The argument for a Q is similar. This completes the proof. 
 Note that if f-| and f 2 both satisfy the conditions of the theorem and 
 f-|(x) - f 2 (x) and f 2 (x) - f-.(x) are both unbounded, then neither of 
 C Q (PTIME, f -, ) and Cq(PTIME, f 2 ) is a proper subset of the other. 
 
 A similar diagonalization argument yields the following result: 
 Theorem 2.3 : Suppose f ? is a computable utilization function. 
 Suppose f 2 is computable in DTIME(g(x)). Also, suppose that 
 
 (\/n >_ l)(3x)f(x) = n. Let F be any recursively enumerable set of monotone 
 nondecreasing total recursive functions. That is, we can enumerate 
 descriptions of Turing machines computing the functions in F. For 
 
-9- 
 
 example, F may be the set of monotone nondecreasing primitive recursive 
 functions. Then there is a language L e C Q (DTIME(g(x) + 1), f 2 ) such 
 that for no f, e F with f 2 (x) - f,(x) unbounded is L e C n (RE, f, ). 
 
 The above results are about the best possible, because of the 
 following fact. 
 
 Theorem 2.4 : If f 2 (x) - f, (x) is bounded, and f 2 (x) > f-i(x), 
 then for all tape complexity classes R, C n (R, f ? ) = C Q (R, f , ) . Also, for 
 some constant c, C Q (DTIME(g(x)), f ? ) c C (DTIME(c*g(x)*logf 2 (x)) , f 1 ) . 
 Similarly, C Q (NDTIME(g(x)) , f £ ) c C (NDTINIE(c*g(x)*logf 2 (x)) , f ) . 
 
 Proof : Suppose L e C Q (R, f ? ). Suppose f 2 (x) - f,(x) ± k 
 for all binary strings x. Suppose T ? accepts L relative to 'the f 2 (x)-utilized 
 oracle B, in complexity class R. We construct a Turing machine T, 
 which simulates T 2 except T-, uses an oracle A such, that A(n) = B(n+k). 
 Whenever T 2 queries B(n), T-j tests if n > k. If so, T-j computes n-k 
 and queries A(n-k). If n <_ k, then T, simulates a query to B using the 
 values B(l), B(2), ..., B(k) stored in a finite control. Testing if 
 n > k and computing n-k will not use any extra tape. However, it may 
 use a number of steps proportional to logn. Hence T-, may need clogn 
 steps for each step of T 2 , and n <_ f 2 (x). The oracle A is B "shifted 
 left" by k bits. 
 
 Note that the proof of Theorem 2.2 still applies if f-,(x) 
 is defined so that for all x with a. < index(x) < a. + ,, f-i(x) = f, (a,- + i ) • 
 Let L be the language of Theorem 2.2. It follows that if L e C Q (RE, f) then 
 there is an infinite set {x,, x 2 , x 3> ...} of binary strings and an infinite 
 set {i-,, i' 2 , i-» . .. } of nonnegative integers such that x. <_a. and such 
 that f(x.) < f 1 (a i ) for all j >_ 1. Thus f(a i ) > f-j (a i ) since f is monotone, and so 
 
-10- 
 
 f (x) 
 lim sup f t x \ 1 1. In general, if g, and g 2 are utilizations and LI 
 
 1 9 ? (x) 
 
 is a language in C Q (RE, g 2 ) - C Q (RE, g^, then lim sup , v > 1. 
 
 We now exhibit a particular Turing machine M for which we can 
 get a lower bound on the amount of oracle needed to solve the halting 
 problem of M for various inputs. 
 
 Theorem 2.5 : Let M be the Turing machine defined as follows: 
 On an input of the form i#x#w, M simulates Turing machine T. on input 
 x using w as the initial portion of a restricted oracle for T.. (Assume 
 Tq, T-j , T 2 , ... is an enumeration of oracle Turing machines, as we have 
 defined them.) Let L M be the set of inputs on which M loops. (Assume 
 M halts if T. tries to use more of the oracle than is contained in w.) 
 Suppose L M e C Q (RE, f). Then lim sup -&- >_ 1 . 
 
 Proof : First we take care of the fact that the inputs to M 
 are not in binary. We encode the i#x# part of the input in binary by 
 the mapping -> 00, 1 ■* 01 , # •*■ 11 . We encode w as it is. This increases 
 the length of the input slightly, but not enough to matter for our purposes. 
 Also, it is easy to extract i, x, and w from this encoding of the input. 
 
 Next we show how a language L e C Q (PTIME, f 2 ) - C Q (RE, f -, ) 
 
 as in Theorem 2.2 can be accepted if an oracle for L„ is available. 
 
 M 
 
 From this reduction it follows that if lim sup | / < 1 then L e C Q (RE, g) 
 
 for some g such that lim sup fjyy < 1> contradicting a remark after 
 
 Theorem 2.4. The idea of the proof is that if L., can be accepted using 
 
 a small amount of oracle, then L can also be accepted using a small 
 amount of oracle. 
 
 For this proof, we choose f-.(x) = |_index(x)/4j - 1 and 
 
 i+2 
 
 f 2 (x) = Lindex(x)/2J. Let the sequence a Q , a-,, a 2 , ... be given by a^ = 2 
 
 Th 
 
 en it follows that f 2 (a i+ -i) - fi(a- + ,) > fo^i^ f° r a H 1 1 and so 
 
-li- 
 
 the construction of Theorem 2.2 can be done with this sequence. We therefore 
 obtain a binary language L with L e C Q (PTIME, f«) - C Q (RE, f, ). 
 
 Suppose fo^-;) < f( x ) 1 fp^'+i^* * n orc ' er t0 decide if x e L, 
 we need to know the behavior of T. on inputs x with index(x) <_ a i+ -i- 
 On such inputs, T. is restricted to use the first fi(a- + ,) bits of its 
 oracle. If we have L» as an oracle, we can test if i#x#A(l )A(2). . .A(f^ (a i+ -|)) e L m 
 to determine if T. loops on input x with f, (x)-utilized oracle A. Also, 
 we can simulate T. directly to see if it halts. By performing these 
 computations in parallel, we can decide if T. accepts x. This is sufficient 
 
 to decide if x e L for some L as in Theorem 2.2. 
 
 Now, the length of the string z = i#x#A(l ). . .A(f,(a. +1 )) will be 
 2(Llog 2 iJ + 1 + |x|) + 4 + f,(a. + , ), by the way this string is encoded. 
 Also, f-,(a. + ,) = 2 1 -1. Furthermore, index(x) f. f-i(a- +1 ) so |x| <_ i . 
 The total length of the string z is then at most 2 + 2i + 2Llog 2 iJ + 5. 
 Now, if L M e C Q (RE, f) then L e C Q (RE, g) where g(a i+] ) = max {f (i#x#A(0) . . .A(2 1+1 -l )) 
 
 a.j < index(x) £a. + ,}. Since f is monotone, this maximum will be attained 
 at index(x) = a i+1 , that is, x = a.. + ,. Thus g(a i+1 ) = f(i#a i+1 #A(0). . .A(2 
 
 We know by above remarks that lim sup r ,L \ > 1. Let z- be the string 
 
 i-x» V a i+l j n 
 
 •4-1 f(z i } 
 
 i#a i+1 #A(0)...A(2 1 -1). Since g(a i+] ) = ffzj), we have lim sup ^-r^ — y l 
 
 Now 
 
 , f } (a i+ i) = 2 |T| -1. Also, | Zi | is 2 ,X| + o(2 ,T| ). Hence 
 
 lim sup f ^ z j) = lim sup f [ z ij 1 z jl > 1. Since lim l z i 1 = 1, 
 i-*=° i+1 i-*» |z. | i+l , i-*» i+l , 
 
 ? _ 1 1 t "• I c. - \ 
 
 lim sup ^ z i ' > 1. This completes the proof. 
 
 I z il 
 
-12- 
 
 We know by Gbdel's incompleteness theorem that in any consistent, 
 sound system of logic that is sufficiently powerful, there are valid 
 formulae that are not provable. Using the above results we can show 
 that such formulae exist that are not ^ery long, "infinitely often". 
 
 Theorem 2.6 : Suppose that F is a sound, consistent system of 
 logic that can express the non-halting of Turing machines on various inputs. 
 Suppose A,, A 2 , A~, ... is a listing of infinitely many "axioms" of F so 
 that F, together with these axioms, is sound and consistent. Suppose 
 
 • n -r- = 0. Then for all e > 0, for infinitely many i, there exists a 
 
 j=T i 1 
 
 Turing machine T and an input z to T such that |T| + |z| < -i-. | A - 1 * (1 + e) 
 
 and such that T loops on z but this fact cannot be proven in F u {A, , Ap, Ag, 
 ....A,}. 
 
 Proof : Let M be the Turing machine in Theorem 2.5. Let A be an 
 oracle listing the axioms A,, A«, A~, ... in order. Assume they are 
 written in binary in such a way that their boundaries can easily be found. 
 We know that if (z: M loops on z} is in C Q (RE, f) then lim sup "tW" - 1 - 
 However, we might be able to partially decide if M loops on z by looking 
 at some of the A. and doing all possible derivations in F. 
 
 Let us assume that for all i, the formulae derivable in F using 
 {A,, A ? , ..., A.} are recursively enumerable. In particular, suppose that 
 there is a Turing machine Tl such that for all i, given {A-, , A 2 » •••, A.}, 
 Tl can enumerate the formulae derivable using Fu {A-,, A 2> ..., A^}. Suppose th 
 the theorem is false. Then there exists e > such that for all but finitely mai 
 if T is a Turing machine and z is an input to T and |T| + |z| < (j £ -| I Aj | )(1 + £ ) , 
 and T loops on input z, then ttie fact that T loops on z can be proven in 
 F u {A,, Ap, ..., A,}. Therefore, we can partially decide if the Turing machine 
 
-13- 
 
 M of Theorem 2.5 loops on z if |M| + |z|<(,L|A.|)(l + e), by doing all possible 
 
 derivations in F u {A 1 , A 2 » . . . , A. }. Let z. be the largest z such that |M|+ j z 1 | 
 
 (-jl-i |A- 1 )(1 + e). The amount of oracle A needed to partially decide if 
 
 z e L» for z < z- is at most - J-. | A - 1 , except possibly for finitely many 
 
 i. Also, |M| + |z.| > (.|-.|A.|)(1 + e) - 1 since z. is as is large as possible. 
 
 1 + |M|+|z. 
 Hence .t } \A.\ < p^ 
 
 1 lA I 1 
 Since |M| is fixed, lim sup j=l ' j ' ±t~+ 
 
 If z. < z < z 
 
 . + , in the lexicographic ordering, then we can partially 
 
 decide if z e L using {A,, A^, ..., A. + ,}. Hence 
 
 tt]|A. 
 
 &i*i 
 
 1 + 
 
 i+1 
 
 ijA. 
 
 IA. 
 
 Since |z|_>|z. | and since 
 
 t Is] I A . | 1 
 — -. approaches zero, we have nm sup j=1 ' j ' ±tt~ 
 
 .LlA.I |7] " e 
 
 j=l ' J 1 ' ' 
 
 Hence L M e C q (RE, f) and lim sup -\~t- ± t+~ , contradicting Theorem 2.5. 
 
 We have exhibited a lower bound on the amount of oracle necessary 
 to solve a particular version of the halting problem. We do not know 
 how good a bound it is. We now exhibit a simple upper bound on the amount 
 of oracle needed to solve another version of the halting problem. The 
 bound in itself is not very significant; we simply give the proof to 
 illustrate the kinds of arguments that can be used to get upper bounds 
 of this type for the halting problem. 
 
 Theorem 2.7 : Let L be the set of descriptions of binary Turing 
 machines T such that T loops on blank tape. Assume these descriptions 
 
 are encoded in the standard way as 5-tuples, and are in binary. Then 
 
 fix) 
 there is a utilization f such that 
 
 lim -j— v 
 index(x)-*» lndex(x) 
 
 and such that 
 
 L e CQ(Recursive, f) 
 
-14- 
 
 Proof : Clearly Tl and T2 are equivalent if they can be obtained 
 
 from one another by permuting their 5-tuples. Also, they are equivalent 
 
 if they can be obtained from one another by a 1 - 1 mapping of state names. 
 
 If the description of Tl is long, then it either has many 5-tuples or else 
 
 some of the binary names for states are longer than necessary. In either 
 
 case, for longer and longer descriptions, there is a smaller and smaller 
 
 fraction of Turing machine descriptions whose halting problem we really 
 
 need to know the answer to in order to decide the halting problem of the others. 
 
 This completes the proof. 
 
 In Theorem 2.2 we showed that a slight increase in the utilization 
 
 of an oracle allows new languages to be accepted. We now prove a result in 
 the other direction. We show that certain languages can be accepted without 
 any oracle, which cannot be accepted in restricted time bounds if an oracle 
 is available with utilization f such that index(x) - f(x) is unbounded. 
 
 Theorem 2.8 : Suppose f is a computable utilization such that 
 index(x) - f(x) is unbounded. Suppose that g(x) is a (total) computable 
 function mapping binary strings into non-negative integers. Then there is 
 a binary language L such that L is recursive but L t C n (DTIME(g(x) ) , f). 
 
 Proof : Let T~, T, , T^, ... be an enumeration of oracle Turing 
 machines. Let aQ, a-,, a^, ... be a monotone increasing sequence of integers 
 such that a Q - f(a Q ) > and such that for all i >. 1, a. +1 - f ( a n - + , ) > a^ . 
 Such a sequence exists because index(x) - f(x) is unbounded. In fact, such 
 a sequence is computable since f is computable. Let T be a Turing machine 
 defined as follows: On inputs x with a- < index(x) <_ a- +1 , T accepts words 
 in a way that T. cannot possibly do regardless of the oracle T^ is using. 
 Note that on such inputs, T. is restricted to the first f(a. +1 ) bits of 
 its oracle. Since a i+ -, - f(a. + -|) > a^ , we have a i+ i - a^ > f(a i+ -|). 
 
-15- 
 
 Hence T has more words to deal with than there are bits of oracle for 
 
 T. to examine, and so T can eliminate all possible oracles for T-. 
 
 Now, given an input x, T finds i such that a. < index(x) <_ a. + -.. 
 
 This is possible since f is computable. T then simulates T. on all 
 
 possible combinations of the first f(a. + ,) bits of the oracle for T. . This 
 
 can be done since T. runs in deterministic time g(z) on input z. If T^ 
 
 tries to use too much oracle, T can eliminate the combination of oracle 
 
 f(a i+1 ) 
 bits that led to that behavior. In the end T has no more than 2 
 
 possible behaviors for T.. Then T chooses a subset of {z: a. < index(z) <. a. + ,} 
 
 to accept which matches none of these behaviors. Finally, T accepts x iff 
 
 x is in this subset. This completes the proof. 
 
 A similar argument yields the following result. 
 
 Theorem 2.9 : Suppose F is a recursively enumerable set of 
 computable utilizations such that for all f e F, index(x) - f(x) is 
 unbounded. Suppose that G is a recursively enumerable set of total 
 computable functions mapping binary strings into non-negative integers. 
 Then there is a binary language L such that L is recursive but for all 
 f e F, for all g e G, L £ C Q (DTIME(g(x)), f). Thus L can be accepted 
 without any oracle at all, but cannot be accepted within time bound g(x) 
 for g e G relative to an f (x)-utilized oracle for f e F. For example, 
 F could be the set of primitive recursive utilizations such that index(x) - 
 f(x) is unbounded for f e F and G could be the set of primitive recursive 
 functions from binary strings into integers. 
 
 The following two results bound the time and space required to 
 accept L, for some language L as in Theorem 2.8. The idea is that in a 
 limited amount of time or space, we can accept a language which cannot 
 be accepted relative to a restricted oracle in some smaller time or space 
 
16- 
 
 bound. Later we will see how this allows us to lower bound the circuit 
 complexity of L. 
 
 Definition : A function s(x) from binary strings to nonnegative 
 integers is constructable if there is a binary Turing machine which uses 
 exactly s(x) tape squares on binary input x. 
 
 Theorem 2.10 : Suppose g(n) is a convex function from nonnegative 
 integers to nonnegative real numbers such that g(n) <_ n for all n, and 
 g(n) < n for some n. Suppose f is a utilization function such that 
 f(x) <. g(index(x)) for all x. Suppose s(x) is a constructable function from 
 binary strings to nonnegative integers, and suppose s(x) _> log(index(x)). 
 Also, suppose |_g(n)J is computable in deterministic space s(n)by some 
 binary Turing machine. Then there is a binary language L such that 
 L t C (DTAPE(s(x)), g(x)) but such that L e DTAPE(0(s(ax) + g(ax))) for 
 some integer a. (We let ax abbreviate the binary string y such that 
 index(y) = a index(x). ) 
 
 Proof : The idea is to bound the space used by the Turing machine 
 of Theorem 2.8. We construct a Turing machine T similar to the Turing 
 machine of Theorem 2.8, such that T accepts L as in the hypotheses and 
 such that T e DTAPE(0(s(ax) + g(ax))). Let the sequence a Q , a,, a 2 , ... 
 of Theorem 2.8 be defined as follows: a. = a 1 where a is some integer such 
 that a - g(a) > 1. Such an a must exist because g is convex, g(0) = 0, and 
 g(n) < n for some n. For convenience, we choose a to be a power of two. 
 This works because if a _> 3, then a - g(a) >_ 3 - g(3). We have a, - g(a-.) > a Q 
 since a - g(a) > 1. Using the fact that g(aa) <_ ag(a) for all a, it is 
 easy to show by induction that a. + , - g(a- + ,) > a. for all i >_ 0. Since 
 a j+-|/a.j is bounded, we never need to simulate Turing machines on inputs 
 
-17- 
 
 that are much larger than the input x to T. This is important for bounding 
 the tape used by T. 
 
 Given input x, T operates as follows: (1) Find i such that 
 a.j < index(x) <.a^ + <i. (Note that i = 1 + Hog index(x)l.) (2) Let T 1 - 
 be the i Turing machine in some standard enumeration T Q , T-, , T~, ... 
 of oracle Turing machines. (Assume that |T. | ~ logi and that T. can be 
 simulated in the same amount of tape that T. uses, plus |T. | tape.) 
 Let S, be {x: a. < index(x) < a. + ,}. Let L(T.) be the language accepted 
 by T . . Find some lanquaqe L. such that L. c S. and such that L(T- ) n S. f L. 
 if J. is in DTAPE(s(x)), regardless of the f (x)-utilized oracle T^ uses. 
 Such a language L- can be found as in Theorem 2.8. (3) Accept x iff 
 x e L • . 
 
 Now, i can be found in 0( log | x | ) tape. .Also, T. can be simulated 
 on a given oracle in tape s(a- + -,) + g(a- + -.). Furthermore, we need 
 1 + gU- + -i) tape squares to store enough of L^ for our purposes. Assuming 
 that s(x) >, log index(x), T uses 0(s(a. + ,) + g(a- + -.)) tape. Since 
 a i < index(x) < a,- + -|. a,- + -| <. ax so T uses 0(s(ax) + g(ax)) tape. This 
 completes the proof. 
 
 In a similar way, we get the following result. 
 
 Definition : A function h(x) from binary strings to nonnegative 
 integers is countable if there is a Turing machine which computes 
 h(x) on input x, and which is ch(x)-time bounded for some constant c. 
 
 Theorem 2.11 : Suppose g(n) and f(x) are as in Theorem 2.10, 
 except that we do not require that Lg(n)J be computable in deterministic 
 space s(n). Suppose h(x) is a countable function from binary strings to 
 nonnegative integers such that h(x) >_ |x|. Suppose |_g(n)j is computable 
 in deterministic time h(n). Then there is a binary language L such that 
 
18- 
 
 L i C (DTIME(h(x)), g(x)) but such that L e DTIME(2 cg ^ ax) h(ax)logh(ax)) for 
 some constant c. 
 
 Proof : Similar to the above, except that we have to be more 
 careful to construct T to be time efficient. The basic idea is that we 
 interleave the description of T. , the oracle A used by T. , and 
 the current tape of T. when simulating T. . Whenever T. moves we move 
 the description of T. and the description of A along with it. 
 The log h(ax) factor comes from the necessity to keep a counter to check 
 how much time T- has used. To find L. , we look through all subsets of 
 {x: a.j < index(x) <_ a. + g(a- + , ) + 1}. Eventually one such subset L. 
 will be found that T. cannot accept in DTIME(h(x)), regardless of the 
 g(x)-utilized oracle T- uses. Also, each subset will only be examined 
 
 for 2 or 3 inputs per oracle on the average before being eliminated. 
 
 g(a. + J 9 (a i+l } 
 
 Since there are about 2 such subsets and about 2 relevant portions 
 
 of oracles, the result follows. We then accept x if x is in L n - , for 
 
 a. < index(x) < a. + , + g(a. + -,) + 1. For other x (if any), it does not matter 
 
 whether we accept or not. This completes the proof. 
 
 We essentially showed in Theorem 2.2 that if f-, and f 2 are utilizations 
 that f 2 is computable and f 2 (x) - f -j (x) is unbounded and (Vn >_l)(3x)f(x) = n, 
 
 then C Q (Recursive, f 2 ) - C Q (RE, f ^ ) is nonempty. We conjecture that the 
 
 probability is zero that an arbitrary language in C Q ( Recursive, f~) is also 
 
 in Cq(RE, f-|) in this case. However, the following result is the best we 
 
 can do so far: 
 
 Theorem 2.12 : Suppose that f-| is a utilization such that 
 
 index(x) - f-j(x) is unbounded. Then the probability is zero that an arbitrary 
 
 language L is in C Q (RE, f,). 
 
-19- 
 
 Proof : Given a Turing machine T', let L ,(T') be {L: there 
 exists an oracTe A for T 1 such that A is f, (x)-utilized by T 1 and such that 
 L is the language accepted by T' relative to A}. Since C~(RE, f , ) is a 
 countable union of L,(T') for various T' , it suffices to show that L, (T 1 ) 
 is a set of measure zero in the set of all binary languages. We do this as follows 
 
 Let a Q , a,, a 2 , ... be a sequence of nonegative integers such 
 
 that a. - f-i(a,-) 1 1 for all i >_ 0. Such a sequence exists because 
 
 index(x) - f(x) is unbounded. Given a binary language L, let pre.(L) be 
 
 {x e L: index(x) < a.}. Let suff.(L) be {x e L: index(x) > a.}. Now 
 
 the distribution of pre^L) will be independent of the distribution of 
 
 a. 
 suff.j(L) over all binary languages L. There will be 2 ] possibilities 
 
 -a- 
 for pre.(L), each with probability 2 of occurring. 
 
 Consider Turing machine T' which uses oracle A. The set 
 
 Ma,) 
 
 {pre. (L): L e L, (T')} has at most 2 elements since L.(T') only 
 
 includes languages accepted relative to an f-,(x)-utilized oracle. (This 
 
 is because T' can only look at the first f,(a.) bits of A on inputs x 
 
 V- MaJ 
 
 with index(x) <^a..) Therefore, at least 2 of the pre.(L) 
 
 for arbitrary binary languages L never occur among {pre.(L): L e L, (T 1 )}. 
 
 Therefore the probability that an arbitrary binary language is in i-.(T') 
 
 f 1 (i i )-a i .. ] 
 
 is at most 2 , which is at most 2 . Since this is true for all i , 
 
 the probability that an arbitrary binary language is in L-.(T') is zero. 
 
 This completes the proof. 
 
 Corollary : Suppose F is a countable set of utilizations such that 
 index(x) - f(x) is unbounded for all f e F. Then the probability that 
 an arbitrary binary language is in f UpC (RE, f) is zero. 
 
 Proof : A countable union of sets of measure zero has measure 
 zero. 
 
■20- 
 
 3. Relationships to Circuit Complexity and the P=NP Question 
 
 Slowly utilized oracles have interesting relationships to 
 Boolean circuit complexity and to the P=NP question. Let Comb(g) be 
 the circuit complexity of a function g: {0, 1 } n -*■ {0, 1} over the basis 
 {a, v, 1}. We regard g as a function from length n binary sequences to 
 {0, 1}. If a circuit C computes g, then we say C accepts a binary string 
 x iff g(x) = 1. In this way we can speak of the (finite) language accepted 
 by a Boolean circuit C. Also, we can discuss the combinational complexity 
 Comb(L) of a set L of binary strings of fixed length. We have the following 
 result. 
 
 Theorem 3.1 : Let L be a binary language. Then L e C Q (PTIME, slow) 
 iff Comb({x e L: |x| = n}) is asymptotically polynomial as a function of 
 n. Thus a language L can be accepted in polynomial time relative to a 
 slowly utilized oracle iff the combinational complexity of fixed length 
 subsets of L is polynomial. 
 
 Proof : If L e c q( p , slow), we can construct polynomial size 
 circuits for {x e L: |x| = n} from the Turing machine and portion of oracle 
 used to accept words in L of length n. If Comb({x e L: |x| = n}) is 
 polynomial, we can construct an oracle containing descriptions of the circuits 
 used to accept words of length 0, 1, 2, ... . Then L can be accepted in 
 polynomial time relative to this oracle by simulating the circuits. Also, 
 
 the oracle will be slowly utilized. Similar results can be shown for larger 
 utilizations and larger combinational complexities. 
 
 Now, "most" functions h: {0, l} n -> {0, 1} have circuit complexity 
 
 near 2 /n [9]. We can use this result to obtain languages that cannot be 
 
 accepted in polynomial time relative to a slowly utilized oracle. In 
 
-21- 
 
 particular, in exponential space we can construct such a language by 
 
 eliminating all languages that can be accepted using small circuits. 
 
 In this way, we obtain the following result: 
 
 Theorem 3.2 : There are languages in EXPTAPE which cannot 
 
 be accepted in polynomial time relative to a slowly utilized oracle. 
 
 Thus, there are yery "hard" languages that can be accepted in 
 
 polynomial time relative to a slowly utilized oracle, and comparatively 
 
 easy languages that cannot. Note that a language which is hard for 
 
 exponential space cannot have polynomial size circuits. Therefore, 
 
 every Turing machine which accepts such a lanauaqe must take more than 
 
 polynomial time on a large number of inputs. To be precise, if L is hard 
 
 for exponential space under polynomial time, linear length increasing 
 
 reductions, then for es/ery Turing machine T accepting L there is a real 
 
 en 
 constant c, c > 0, such that T requires an average of at least 2 time 
 
 on inputs of length n for large enough n. This can be shown using the 
 
 usual circuit complexity techniques [9]. We do not know if this is also 
 
 true of deterministic or nondeterministic exponential time. We can obtain 
 
 similar results for languages complete for other time or tape complexity 
 
 classes by usina Theorems 2.10 and 2.11, together with extensions of 
 
 Theorem 3.1 . 
 
 The following result shows that slowly utilized oracles can 
 be found in PSPACE, if they exist. 
 
 Theorem 3.3 : There is a Turing machine T which, given any 
 language L e C q (P, slow), can construct an oracle B such that 
 L e Cq(P, slow, B). -This constru6ttion can be doee 'in DaiTynonijal- 
 space. (We assume L is itself given to T as an unrestricted oracle.) 
 
-22- 
 
 Proof : The Turing machine T finds the smallest Boolean 
 
 circuit C which will accept {x e L: Ixl = n}. The oracle B is then a 
 n 
 
 sequence of descriptions of C Q , C-j , C£ If L e C Q (P, slow) 
 
 then polynomial size circuits exist and so T will run in polynomial space. 
 
 This result implies that if L is PSPACE-hard, then finding a 
 slowly utilized oracle B for L is not much harder than accepting L. 
 It is interesting, however, that there 1s no general procedure to decide 
 if a recursive language 1s Tn C ("P, slow). 
 
 Theorem 3.4 : There is no procedure which, for all Turing 
 machines T that halt on all inputs, decides whether the language accepted 
 by T is in C Q (P, slow). 
 
 Proof : By reduction from the halting problem. Given arbitrary 
 Turing machine T-, , we construct T so that the language accepted by T is 
 not in Cq(P, slow) iff T, halts on blank tape. Let L be the language 
 accepted by T. The idea is to construct T so that L n {x: |x| = n} has 
 a small circuit iff T, does not halt within n moves when started on blank 
 tape. Now, T can decide if T, halts in n moves or less by simulation. 
 If T, does not halt, T accepts all words of length n. If T, does halt, T 
 can in exponential space find a language L consisting of binary words of 
 length n such that L has no small circuit. Then T accepts an input x 
 of length n such that L has no small circuit. Then T accepts an input 
 x of length n iff x e L . Note that T runs in exponential space. 
 
 We now show that the complexity theoretic properties of restricted 
 oracles are quite different than thoseof unrestricted oracles. In particular, 
 it is known [ 2 ] that P = NP relative to some unrestricted oracles and P + NP 
 relative to others. We show that deciding whether P = NP relative to any 
 slowly utilized oracle would have profound implications for our understanding 
 of the unrelativized P = NP question. 
 
■23- 
 
 Theorem 3.5 : Every problem in NP has polynomial size circuits iff 
 there exists an oracle A such that C«(P, slow, A) = Cq(NP, slow, A). 
 
 Theorem 3.6 : P t NP iff there exists an oracle A such that 
 C Q (P, slow, A) f C Q (NP, slow, A). 
 
 Proof of Theorem 3.5 : Suppose A is an oracle such that C n (P, slow, A) = 
 C Q (NP, slow, A). Then any problem S in NP is in C~(NP, slow, A) hence is in 
 C n (P, slow, A) hence has polynomial size circuits. 
 
 Suppose all problems in NP have polynomial size circuits. Let A 
 
 be an oracle listing the circuits C, , C ? , C~, ... where C is the circuit 
 
 for inputs of length i to some fixed NP-complete problem T. Suppose 
 
 SI e C Q (NP, slow, A). We show that SI e C Q (P, slow, A). Let S2 be 
 
 {< x, AD : x e SI and Al is the portion of A available for input x}. Since 
 
 SI e C Q (NP, slow, A), S2 e NP. We can reduce S2 to T in polynomial time, and 
 
 then solve T in polynomial time using A slowly. Thus, SI can be reduced to 
 
 T if A is available as a slowly utilized oracle, and T can be solved in 
 polynomial time if A is available as a slowly utilized oracle. Hence 
 
 SI e c q( p > s 1° w > A )- This completes the proof. 
 
 Proof of Theorem 3.6 : Suppose P f NP. Choose A to be the trivial 
 oracle consisting of all zeroes. Then C Q (P, slow, A) = P and C Q (NP, slow, A) = NP 
 
 Suppose there exists an oracle A such that C Q (P, slow, A) f 
 C Q (NP, slow, A). Suppose SI is a problem in C Q (NP, slow, A). Let S2 be 
 obtained from SI by appending suitable portions of A to the inputs to SI. 
 Then S2 e NP . Also, the reduction from SI to S2 can be done in polynomial time 
 relative to A slowly utilized. If P = NP, then S2 e P hence SI E C Q (P, slow, A) 
 so C Q (P, slow, A) = C Q (NP, slow, A). Contradiction. Therefore, P f NP if 
 C Q (P, slow, A) f C Q (NP, slow A). 
 
-24- 
 
 The following results can easily be obtained by similar methods. 
 
 Theorem 3.7 : If C Q (P, slow) = C Q (NP, slow) then every language in 
 NP has polynomial size circuits. 
 
 Theorem 3.8 : If C Q (P, slow) f C Q (NP, slow) then P f NP. 
 
 Results similar to this can be obtained for C n (P, f, A) and 
 C n (NP, f, A) if f(x) is sufficiently smaller than index(x), but still 
 larger than log(index(x)) for any k. It would be interesting to see how 
 much of a restriction on oracles can be made while still being able to decide 
 the P = NP question for specific oracles. 
 
 Definition : A problem S is NP-complete relative to slowly utilized 
 oracle A if S e Cq(NP, slow, A) and if every other problem in C Q (NP, slow, A) 
 can be reduced to A in polynomial time. 
 
 Theorem 3.9 : Suppose S is NP-complete relative to a slowly utilized 
 oracle A. Then if S e C (P, slow, A) every problem in NP has polynomial size 
 circuits, and if S i C Q (P, slow, A) then P f NP. Also, if S has polynomial 
 size circuits, then so do all problems in NP. 
 
 Proof : By above remarks and properties of circuit complexity. 
 
 In [8] we presented some problems that are NP-complete relative 
 to a particular slowly utilized oracle if we allow polynomial time 
 reductions which utilize the oracle slowly. We now present complete 
 problems relative to an arbitrary oracle, in which the reductions are not 
 relativized. 
 
 Definition : If R is a complexity class and A is an oracle, 
 
 n 
 
 then R is the relativized complexity class. Here A is an unrestricted 
 
 A A 
 oracle. We thus obtain P , NP et cetera as usual. 
 
-25- 
 
 Definition : A problem S is NP-complete relative to oracle A 
 
 A A 
 
 if S e NP and if every other problem in NP can be reduced to S in 
 
 polynomial time by a many-one reduction. 
 
 Suppose A is a binary oracle, that is, a subset of (0+1)*. 
 Let Rn(y> x-|,...,x ) be the binary relation defined so that 
 Rfl(y» x,, ..., x ) is true if y = 1 and x e A or if y = and x t A. Here 
 x is the binary string x,x«...x . Note that R« has a variable number of 
 arguments. We consider to be the truth-value FALSE and 1 to be TRUE. 
 The relativized satisfiability problem is the following: Given a Boolean 
 expression E involving Boolean variables, the connectives A (and), v (or), 
 and ~1 (not), and the relation R., to decide if E is satisfiable. 
 
 Theorem 3.10 : The relativized satisfiability problem for oracle 
 A is NP-complete relative to A. 
 
 Proof : Similar to Cook's proof [3] that satisfiability is 
 NP-complete. The idea is to simulate the computation of a nondeterministic 
 Turing machine by a Boolean expression, using the relation R- to simulate 
 queries to the oracle. Also, it is clear that the relativized satisfiability 
 problem is in NP . 
 
 Undoubtedly many other NP-complete problems have relativized 
 versions that are NP-complete relative to an oracle. We now exhibit a 
 problem that is complete for Cq(NP, slow, A) for arbitrary A. 
 
 Theorem 3.11 : The following problem is complete for Cp.(NP, slow, A) 
 under polynomial time reductions: Given a Boolean expression E involving 
 Boolean variables, the Boolean connectives a, v, "1, and "oracle variables" 
 of the form A(j) where j is in unary notation, to decide if E is satisfiable 
 when A(j) is replaced by 1 if j e A and by if j i A. (Recall that j 
 is the binary string x such that index(x) = j.) 
 
-26- 
 
 Proof : Corresponding to any S in Cq(NP, slow, A) there is a 
 problem in NP obtained by appending a suitable portion of the oracle A to 
 inputs to S. This latter problem can then be converted to a Boolean expres- 
 sion as above by the usual methods. Note that the oracle queries are fixed 
 in this problem rather than variable as in the relativized satisfiability 
 problem. 
 
 Theorem 3.12 : The following problem is complete for PS PACE 
 under polynomial time reductions: Given a quantified Boolean expression E 
 in which the relation R» may also occur, to decide if E is true. 
 
 Proof : By methods similar to the above, and to those used in 
 
 [11]. 
 
 Theorem 3.13 : The following problem is complete for C Q (PSPACE, 
 slow, A) under polynomial time reductions: Given a quantified Boolean 
 expression E in which A(j) as above may occur as variables, to decide 
 if E is true. 
 
 Proof : Similar to the proof of Theorem 3.12. 
 
 Theorem 3.14 : The following problem is complete for P under log 
 tape reductions: Given an acyclic circuit in which the functions A, v, ~1, 
 and f A are allowed, and given 0, 1 inputs to the circuit, to decide if the 
 output is 1. We define fn(x-., x~, ..., x ) to be 1 if x-,x 2 ...x eA, 
 otherwise. This function also has a variable number of arguments. 
 
 Proof : By simulating a deterministic Turing computation as in 
 [6], using f. to simulate queries to the oracle. 
 
 Theorem 3.15 : The following problem is complete for Cq(P, slow, A) 
 under log tape reductions: Given an acyclic circuit with functions 
 A, v, ~l allowed and with values 0, 1, or A(j) specified for each input, 
 to decide if the output is 1. Here j is in unary and A(j) is considered to 
 be 1 if j e A, otherwise. 
 
■27- 
 
 Proof : Similar to the above. 
 
 Theorem 3.16 : The following problem is complete for NLOGSPACE 
 under log tape reductions: Given a directed graph G with vertices 
 {1, 2, ..., n}, and with some edges labeled A(j) and others labeled A( j) , 
 to decide if there is a path from 1 to n in G satisfying the following 
 condition: If j e A then no edge labeled A(j) may be in the path, and 
 if ] i A then no edge labeled A(j) may be in the path. Here A(j) is 
 as above, with j in unary. 
 
 Proof : Applying the usual reduction [10] to show the graph 
 accessibility problem is complete for NLOGSPACE. It is sufficient to have 
 j in unary in A(j) because a log tape bounded Turing machine can only 
 utilize A slowly. The labeled edges allow transitions between "configurations" 
 to be possible or not depending on the outcome of queries to A. 
 
 Note that if A e NP n CoNP then NP A = NP and CoNP A = CoNP. 
 Also, if A e NLOGSPACE n CoNLOGSPACE then NLOGSPACE A = NLOGSPACE and 
 CoNLOGSPACE A = CoNLOGSPACE. Therefore P f NP if there exists an oracle 
 A such that P A f NP A and such that A e NP n CoNP. It is interesting that 
 the oracle in [2] relative to which P f NP, is not far from being in P. 
 Also, NP f CoNP if there exists A e NP n CoNP such that NP A f CoNP A . Similarly, 
 DLOGSPACE f NLOGSPACE if there exists A e NLOGSPACE n CoNLOGSPACE such 
 that DLOGSPACE A f NLOGSPACE A . Finally, NLOGSPACE f CoNLOGSPACE if there 
 exists A as above such that NLOGSPACE A f CoNLOGSPACE A . 
 
 If B is an oracle relative to which P / NP, then the satisfiability 
 problem relative to B cannot be solved in polynomial time, even if B is 
 available. This is an interesting case in which we can show a satisfiability 
 problem not to be in P. 
 
-28- 
 
 4. Compressibility 
 
 We now consider another aspect of restricted oracles. If 
 
 L e C Q (Recursive, f) then L can be compressed by f, in some sense. 
 
 Given L, we might ask how much it can be compressed? Is it true that 
 
 most functions cannot be compressed much? Or we might ask what is the 
 
 smallest f such that h e C Q (PTIME, f)? Such questions lead to the 
 
 definition of compressibility, which is an interesting alternative to 
 Kolmogorov complexity of finite sequences [5] and to the program complexity 
 
 of finite functions [9]. Undoubtedly there are many relationships between 
 
 compressibility and these other complexity measures. 
 
 Definition : We say f is a compressibility for L if L e C Q ( Recursive, f) 
 
 and 1f for all f , L e C Q (Recursive, f) implies f(x) is 0(f'(x)). 
 
 Theorem 4. 1 : For all languages L, there exists a utilization 
 
 f such that f is a compressibility for L. In fact, with notation as 
 
 above, we have f(x) <_ (4+e)f (x) for large x. 
 
 Proof : By piecing together oracles and Turing machines 
 
 for L. Given L, we "construct" an oracle A and a compressibility f for 
 
 L. The oracle A for L is of the form M,a,M 2 a 2 M„a 3 . . . where M. is the 
 
 description of some Turing machine and a. is the initial portion of some 
 
 oracle A. for M. . Also, let f. be the utilization function for A^ by M i . 
 
 Each Turing machine M. accepts L relative to the f • (x)-utilized oracle 
 
 A.j, except that some of the M- for small i may be blank (i.e., for 
 
 some m). We construct T which accepts L using A. Given an input x, T 
 
 finds the least i such that M. is not blank. The Turing machine T then 
 
 simulates M. on x. If M. tries to use more of A. than contained in a., 
 i i i i 
 
 then T simulates M. + , on x, and so on. 
 
-29- 
 
 The strings M. and a. are chosen so that the length of M. 
 is 2 L1/ J and the length of « i is 2 1 . If necessary, the description 
 of M. is padded with leading or trailing zeroes. Also, M. is chosen 
 so that max{x: f^x) <_ 2 } is as large as possible among Turing machines 
 with small enough descriptions. Let f(x) be the utilization of A by T. 
 Note that f may not be computable unless A is available. We claim that 
 
 if Turing machine M accepts L relative to g(x) -utilized oracle B, then 
 
 f (x) 
 lim sup 44< 4. Hence f(x) is 0(g(x)) as claimed, and f is a com- 
 pressibility for h. 
 
 We show this as follows. For large enough i, the description 
 
 of M will fit in 2 1 spaces. Hence for all j >_ i , max{x: f.(x) < 2 J } >_ 
 
 •J 
 
 max{x: g(x) < 2 J } . Suppose f.(x) > 2^ and f. + ,(x) ^2 : ' +1 . Then 
 
 g(x) > 2 J also. However, f(x) will be not much more than 2 , so 
 
 f(x) 
 
 —j— j will be not much larger than 4. This completes the proof. 
 
 We can extend this result. 
 
 Definition : We say f is a partial compressibility for L if 
 L e C Q (RE, f) and if for all f , L e C Q (RE, f ' ) implies f(x) is 0(f'(x)). 
 
 Theorem 4.2 : For all languages L, there exists a utilization 
 f such that f is a partial compressibility for L. In fact, with notation 
 as above, we have f(x) <_ (4+e)f'(x) for large x. 
 
 Proof : Similar to the above proof. In a sense, partial 
 compressibility corresponds to the size of the list of axioms that are 
 needed to derive an infinite set of theorems. We will return to this 
 point later. 
 
 It is not difficult to show that if f, is a compressibility for 
 LI and f„ is a compressibility for L2, then max(fpfo) is cwvs-pper bound for 
 
-30- 
 
 the compressibility of LI u L2 and for LI n L2. The idea is to construct 
 an oracle which has the LI oracle as its odd bits and the L2 oracle as 
 its even bits. Similar comments apply to partial compressibility. 
 
 We cannot quite get compressibilities for restricted time and tape 
 bounds, but we can come close, as the following results show. 
 
 Theorem 4.3 : Let g(x) be a function from binary strings to nonnegative 
 
 integers such that g(x) _> 2|x|. Suppose x < y implies g(x) <_ g(y). (We are 
 
 using the lexicographic ordering on strings as before.) Let DTIME(g(x)) 
 
 denote the deterministic Turing machines which use no more than g(x) steps on 
 input x. Suppose L is a binary language. Then there is a utilization f and a 
 
 constant c > such that L e C Q ( DTIME(c | x | 2 *g(x) ) , f) and such that if 
 
 L e C (DTIME(g(x)), f) then f(x) is 0(f'(x)). 
 
 Proof : By the construction given above. Since g(x) >_ 2|x|, we 
 
 know that L e C Q (DTIME(g(x)) , index(x)). Choose M. and a. so that M. accepts 
 
 L in DTIME(g(x)) relative to f.j(x)-utilized oracle A. having a. as a prefix, 
 
 and so that {x: f.(x) j< 2 1 } is as large as possible subject to the condition 
 
 |M. | <_ i . We choose |a. | = 2 1 as before and so M. + , is never used unless 
 
 me) 
 
 f.(x) > 2 1 . However, since index(x) _> f.(x), we have index(x) > 2 1 and 
 |x| > i-1 when M. + , is used. The number of simulations we need to do is therefore 
 never more than |x| +2. It is easy to see that we can skip the first two simulatia 
 and so the number of simulations is never more than |x|. Also, since g is monotoi 
 each simulation will take g(x) or less simulated steps for a total time of 
 |x|g(x) simulated steps taken by T. We slightly modify the construction of 
 
 Theorem 4.1 so that each simulated step takes proportional to |x| actual 
 
 steps of T. Also, erasing the tape when shifting to a higher i takes proportional 
 
 to g(x) steps. Hence the total time is c|x| g(x) steps for some constant c. 
 
-31- 
 
 The simulated steps take longer because of the necessity to shift the description 
 of M. along the tape when doing the simulation, and also because of the 
 fact that queries to a. must be modified to obtain queries to A. We deal with 
 the first problem by requiring that |M. | <_ i. Note that this does not affect 
 
 Theorem 4.1 but does allow shifting to be done in about |x| steps since i 
 
 i+2 
 can never be much larger than |x|. We require that a- begin on the 2 
 
 bit of A to simplify the modification of queries. This requires that unused 
 
 gaps exist in A. However, this only increases the utilization by a constant 
 
 factor (at most 2). It is then only necessary to add 2 1 to an a. query to get 
 
 an A query. The time required is proportional to i, or, to |x| as above. 
 
 Hence each simulation step takes proportional to |x| actual steps. Also, the 
 
 description of M. can be copied to the work tape in 0(i ) moves. The total 
 
 time for copying may be 0(|x| ) but this does not matter, because g(x) >_ |x|. 
 
 Furthermore, the utilization f(x) of A by T is 0(f'(x)) as before. This 
 
 completes the proof. 
 
 By similar methods, we can show the following result: 
 
 Theorem 4.4 : Let g(x) be a function from binary strings to nonnegative 
 
 integers, such that x < y implies g(x) < g(y). Suppose that g(x) >_ |x|. 
 
 Suppose L is a binary language. Then for all e > there is a utilization f 
 
 such that L e C Q (DTAPE( (1 +e)g(x) ) , f) and such that if L e C Q (DTAPE(g(x) ) , f) 
 
 then f(x) is 0(f'(x)). 
 
 Proof : Since g(x) > |x|, L e C Q (DTAPE(g(x)) , index(x)). The factor 
 
 of (l+e)g(x) gives enough space to store the description of M. when doing the 
 
 simulation. The description of M. will be stored at the beginning of the 
 
 nonblank portion of the work tape, with its boundary indicated in some reasonable 
 
 way. The rest of the argument is similar to that of Theorem 4.3. 
 
-32- 
 
 Restricted Sets of Axioms 
 
 Just as we can talk about slowly utilized oracles, so we can discuss 
 slowly utilized sets of axioms. It could be that no finite set of axioms 
 suffices to derive all the valid formulae of some logical theory F, but that 
 the number of axioms needed grows slowly as a function of the size of the formula 
 one is trying to prove. We say that the valid formulae of F can be derived 
 relative to a slowly utilized set of axioms if there exists k such that the total 
 length of the axioms needed to prove all valid formulae of length m or less 
 is never more than m . We relate slowly utilized sets of axioms to slowly 
 utilized oracles. In particular, we consider the "axioms" to be productions 
 in some grammar, and we consider the "formulae" to be words in some language. 
 
 However, the grammar may have infinitely many productions. 
 
 Theorem 5. 1 : A language L can be derived using a slowly utilized 
 
 set of productions of type 0, iff L e C q (RE, slow). 
 
 Proof : Suppose L e C Q (RE, slow). Let T be some Turing machine 
 
 accepting L using slowly utilized oracle A. We assume that the input tape 
 and working tape of T are all combined into one tape. Clearly this does 
 
 not slow T down by much. 
 
 We assume that before T accepts, it erases everything on 
 
 the tape. This can always be done. We then construct a grammar G which 
 
 simulates the operation of T "in reverse". Hence if a word is derivable 
 
 in G, the word is accepted by T, and vice versa. The productions of G 
 
 are derived from the transitions of T as usual. That is, if T in state 
 
 q scanning an a enters state r, writes b, and moves right, then we have 
 
 br -> qa as a production. If T in state q scanning an a enters state r, 
 
 writes b, and moves left, then we have rcb ■*■ cqa for all tape symbols c. 
 
-33- 
 
 We also need productions to add blanks at either end of a configuration 
 when necessary and to delete blanks from either end when necessary. In 
 addition, we have a slowly growing set of productions for the oracle A. 
 These productions are of the form q Q aa ■* qaa or of the form q-jcta ■* qaa. 
 Here q is an "oracle state", representing a query to the oracle. Also, 
 a is a binary string and a is an end marker. If A(a) = then q Q aa ■* qaa 
 is included in the grammar. If A(a) = 1 then q-jaa -> qaa is included in 
 the grammar. This corresponds to a query to A, in which the value a is 
 written immediately to the right of the Turing machine's read-write head. The 
 Turing machine enters state q~ or q, depending on whether A(a) = or 
 A(a) = 1. It is easy to see that such a grammar can derive L, using only 
 a slowly growing number of productions. 
 
 Conversely, if L can be derived using a slowly utilized set 
 of productions, let A be an oracle listing these productions in the 
 appropriate order. Then L e Cq(RE, slow, A) since a Turing machine can try 
 all possible derivations using the allowed productions. 
 
 The class C~(NPTIME, slow) is interesting in this respect. 
 It represents the languages which can be derived using short derivations 
 of a slowly utilized set of productions. It would be interesting to 
 know whether CoNP c C~(NPTIME, slow). If so, short proofs of inconsistency 
 could be supplied using a slowly utilized oracle. 
 
 The intuition behind this concept is that as mathematics 
 advances, more and more theorems will have short proofs relative to a 
 slowly growing set of axioms and inference rules. Mathematics would 
 not be very interesting if "new knowledge" were needed to prove each 
 new theorem. On the other hand, it seems that the "useful results" 
 in mathematics will increase without limit. The concept of a slowly 
 
-34- 
 
 utilized set of productions captures the idea of a useful, but 
 infinite, set of mathematical knowledge. 
 
 6. Restricted Sequences of Turing Machines 
 
 There is another approach to this problem of slowly growing 
 
 knowledge. Suppose as mathematics progresses, better and better theorem 
 
 proving procedures are found for some infinite set of formulae. Suppose 
 
 that each such procedure is fairly small and is able to handle all formulae 
 
 up to a certain size. Even if no general decision procedure exists, it 
 could be that reasonable procedures exist for larger and larger formulae. If 
 
 a few short formulae cannot be decided by such a procedure, we can imagine 
 these being kept in a table of special cases to obtain a complete procedure 
 for small formulae. We now show that such ideas are also related to the 
 concept of restricted oracles. In particular, if for all n, small programs 
 exist to recognize valid formulae of length n (possibly a different procedure 
 for each n), then valid formulae of arbitrary length can be recognized relative 
 to a slowly utilized oracle. 
 
 Definition : Suppose we have a method of encoding Turing machines 
 as binary strings so that 
 
 a) a universal Turing machine can carry out simulations with 
 at most a polynomial increase in time, and 
 
 b) there is a polynomial p such that any subset of the binary 
 strings x with 1 <_ index(x) <_ n, can be recognized by some 
 Turing machine whose description is no more than p(n) bits long 
 
 Note that common encodings of Turing machines have properties a) and b). 
 Let C p (R, f) be the set of binary languages L such that for all n >_ 1, 
 L n {x: index(x) <_ n} can be accepted by a Turing machine M whose 
 description is no more than f(n) bits long. We assume f(n) £p(n). 
 
 
-35- 
 
 We also require M to be in complexity class R. In addition, M must 
 
 behave as follows: If index(x) > n, then M must halt and reject, scanning 
 
 a tape square containing a zero. If index(x) <^n, then M either accepts 
 
 x or M loops or M halts scanning a tape square containing a one. This 
 
 enables us to tell whether index(x) > n if M halts and rejects. The P in 
 
 n 
 
 C p stands for "program size." 
 
 Theorem 6.1 : C p (PTIME, f(x)) is a subset of C Q (PTIME, 4*f(x)) 
 for all f with f(x) <_ p(x). 
 
 Proof: Suppose L e C p (PTIME, f). Then L e C p (q(x), f(x)) 
 
 for some polynomial q. Let M. be Turing machines as above whose descriptions 
 
 require no more than f(i) bits, such that M. accepts L n (x: index(x) <_ i} 
 
 and requires time q(i) or less on all x such that index(x) < i. Let 
 
 | M | denote the length of the description of a Turing machine Nl. Assume 
 
 l M i + -il L l M -jl f° r a ^ i« Also, assume that the |M. | are unbounded. If 
 
 the |M. | are bounded, a similar argument applies. Note that f(x) >_ |M |. 
 
 Construct sequence N, , N ? , N 3 , ... of Turing machines as follows: N. = M 
 
 where a,, a ? , a-, ... is a monotone increasing sequence of integers. 
 
 Choose a, = 1. For i > 1, a.,, = max{j: |M.| < 2*|M .,|}. This maximum 
 i i + 1 j a • + 1 
 
 exists because |M.|is unbounded. Thus a. + -, is chosen as large as possible 
 
 so that 
 
 K I < 2|M | (1) 
 
 a i+l k 
 
 for k = a-j + 1. Note that this implies that 
 
 a i + 1 ^a i + l (2) 
 
 and 
 
 and 
 
 l M a i+1 + l' >2 l M a i + ll 0) 
 
 a i+l ' a i+l 
 
-36- 
 
 Let A be the oracle containing descriptions of N, , N ? , N-, ... in that order. 
 
 Assume the descriptions are encoded so that we can easily find their boundary, 
 
 Let T be a Turing machine which does the following: On input 
 
 x, T simulates N, , Np, N.,, ... in order until it finds a Turing machine 
 
 N., which does not halt and reject scanning a zero. This means that 
 
 a. i < index(x) < a^, and x is not too large for N.. Then T simulates N. 
 
 and uses the result of the simulation to decide whether to accept x or not. 
 
 The amount of oracle used is .£, N.. We know that index(x) >^ a- -. + 1 so 
 
 f(x) > |M | > |M_ +1 |. By (1) above, |M | < 2|M ,, | so 
 x a i _ 1 f i ai a^-, + 1 
 
 |M a | < 2f(x). (5) 
 
 a 
 
 i 
 
 Also, a. i < index(x) so |M, < f(x) by (4). Further, 2|M a ,| < 
 i-l a i _ 1 a i-2 ' 
 
 ,, I et cetera Dy \j) . inus 
 l i-l r| a i-3" a i-2 
 
 +1 |, 2 jM a j | < |M a> ^ et cetera by (3). Thus .l\ |M fl>+1 
 
 2|M a +l| < 2f(x). However, |M a I < |M a . , | by (4) and so ]z]|M. | < 2f(x). 
 a i-l " a j a j J ~' a j 
 
 Combining this with (5), .J, |M < 4f(x), and the oracle is 4*f(x) 
 
 J- 1 a- 
 
 utilized as claimed. Since N. <_ p(x), i is O(logx). Thus there will 
 be at most O(logx) simulations, each taking no more than q(y) steps for 
 some y < x. Each step of the simulation may take more than one time unit, 
 but simulation only causes a polynomial increase in time and so we still 
 get a polynomial time bound overall. 
 
 We can also get an easy bound in the other direction. 
 
 Theorem 6.2 : Assuming Turing machines are encoded in the standard 
 way as sets of quintuples represented in binary, then there is a polynomial 
 r(x) such that C Q (PTIME, f(x)) is a subset of U m C p (PTIME, r(f(x)+m)). Here 
 m is a non-negative integer. 
 
-37- 
 
 Proof : Suppose L e C n (PTIME, f(x)). Suppose Turing machine T 
 accepts L relative to the f(x) -utilized oracle A. Also, T runs in 
 polynomial time. Let m be the length of the representation of T. We 
 construct T which simulates T on inputs x with index(x) <_ n. Whenever T 
 consults its oracle, T uses a set of about f(n) special states, arranged 
 in a tree, to compute the value of the oracle. Since T runs in polynomial 
 time, T does also. In addition, if we are given the value f(n), the 
 values A(l), A(2), ..., A(f(n)), and a description of T, a description of 
 T can be obtained in polynomial time. Therefore the length of the description 
 of T is polynomial in m and f(n), as claimed. This completes the proof. 
 
 The meaning of this result is that if a language L can be 
 accepted in polynomial time relative to an f (x)-utilized oracle, then 
 {y e L: index(y) < index(x)} can be accepted in polynomial time by Turing 
 machines which are not much larger than f(x). 
 
 7. Relations to Randomness 
 
 Adleman recently showed [1] that any problem which can be 
 
 done in "random polynomial time" has small circuits. From our results 
 it follows that polynomial time together with slowly utilized oracles 
 
 is at least as powerful as random polynomial time. In fact, this class 
 is much more powerful since C n (P, slow) contains functions at all 
 levels of the recursive hierarchy, and random polynomial time is a subset 
 of exponential time. 
 
 As another connection, we consider pseudo-random number generators. 
 Let us call a function f from non-negative integers into {0, 1} a pseudo- 
 random number generator if the sequence f(0), f(l), f(2), ... has desirable 
 randomness properties. In particular, the function f should not have 
 
38- 
 
 polynomial size circuit complexity. Also, to be practical, f(x) should 
 be computable in polynomial space. (Polynomial time is not necessary 
 since f(x) is usually computed from a small number of values f(x-j) 
 
 for small values of j.) We have the following unexpected result: 
 
 Theorem 7. 1 : If any pseudo-random number generator f as described 
 
 above exists, then PSPACE f P. 
 
 Proof : The function f is in PSPACE, but cannot be in P since 
 it does not have small circuits. 
 
 This result suggests that when looking for particular functions 
 with exponential circuit complexity, we should look for functions which 
 behave like "random" functions. 
 
 8. Relation to Sparse Oracles 
 
 Albert Meyer has obtained some results relating circuit 
 complexity to sparse oracles [7]. In particular, he has shown that a 
 function has small circuits iff it can be computed in polynomial time 
 relative to a sparse oracle. Restricted oracles are therefore closely 
 related to sparse oracles. It would be interesting to see if there are 
 results for sparse oracles corresponding to the results for restricted 
 oracles. 
 
 9. Conclusions 
 
 Restricted oracles have interesting relationships to many 
 areas of complexity theory. Much more work can be done in this area. 
 For example, we can consider the utilization of an oracle on various 
 subsets of the inputs. The results presented here can be refined. Also, 
 
39- 
 
 it would be interesting to exhibit natural, unsolvable problems that can 
 be decided in deterministic or nondeterministic polynomial time relative 
 to a slowly utilized oracle. In addition, we may get new hierarchies by 
 using as restricted oracles, languages that are themselves accepted using 
 restricted oracles. We might also construct more complete problems 
 in Cq(R, f, A) for various R, f, and A. Such problems were discussed in 
 [8]. Finally, we may ask how compressible various unsolvable problems 
 (such as the halting problem) are. We have presented a lower bound on 
 the compressibility of one version of the halting problem. 
 
-40- 
 
 References 
 
 1. L. Adleman, Two theorems on random polynomial time, Proceedings of the 
 19th Annual Symposium on Foundations of Computer Science (1978), 75-83. 
 
 2. T. Baker, J. Gill, and R. Solovay, Relativizations of the P = ?NP question, 
 SIAM J. Computing 4(1975), 431-442. 
 
 3. S. Cook, The complexity of theorem proving procedures, Proceedings 
 of the 3rd Annual ACM Symposium on Theory of Computing (1971 ), 
 151-158. 
 
 4. J. Hopcroft and J. Ullman, "Introduction to Automata Theory, Languages, 
 and Computation", Addison-Wesley, Reading, Mass., 1979. 
 
 5. A. Kolmogorov, Three approaches to the quantitative definition of 
 information, Probl. Peredachi Inf . 1(1965), 3-11. 
 
 6. R. E. Ladner, The circuit value problem is log-space complete for P, 
 SIGACT News 7:1 (1975), 18-20. 
 
 7. A. R. Meyer. Cited in J. Hartmanis and L. Berman, on isomorphisms and 
 density of NP and other complete sets, Proceedings of the Eight Annual 
 ACM Symposium on Theory of Computing , Association for Computing Machinery 
 
 aim by IT 
 (1976), 
 
 30-40. 
 
 8. D. Plaisted, New NP-hard and NP-complete polynomial and integer 
 divisibility problems, Proceedings of the 18th Annual Symposium on 
 Foundations of Computer Science (1977), 241-253. 
 
 9. J. Savage, "The Complexity of Computing", Wiley, New York, 1976. 
 
 10. W. J. Savitch, Relationships between nondeterministic and deterministic 
 tape complexities, J. Computer and Systems Sciences 4 (1970) 177-192. 
 
 11. L. J. Stockmeyer and A. R. Meyer, Word problems requiring exponential 
 time, Proceedings of the 5th Annual ACM Symposium on Theory of Computing 
 (1973), 1-9. 
 
BIBLIOGRAPHIC DATA 
 SHEET 
 
 1. Report No. 
 
 UIUCDCS-R-79-995 
 
 4. Title and Subtitle 
 
 Restricted Oracles 
 
 3. Recipient's Accession No. 
 
 5- Report Date 
 
 October 1979 
 
 6. 
 
 1. Author(s) 
 
 David A. Plaisted 
 
 8. Performing Organization Rept. 
 
 No. 
 
 t. Performing Organization Name and Address 
 
 Dept. of Computer Science 
 222 Digital Computer Lab 
 University of Illinois 
 Urbana, IL 61801 
 
 10. Project/Task/Work Unit No. 
 
 11. Contract /Grant No. 
 
 NSF MCS 77-22830 
 
 12. Sponsoring Organization Name and Address 
 
 National Science Foundation 
 Washington, D.C. 
 
 13. Type of Report & Period 
 Covered 
 
 14. 
 
 15. Supplementary Notes 
 
 Abstracts 
 
 An oracle for a Turing machine is restricted if the amount of oracle 
 that may be examined on inputs of a given size is restricted in various ways. 
 This concept yields interesting hierarchies for solvable as well as for unsolvable 
 problems. One of these hierarchies is used to get lower bounds on the sizes of 
 the axioms needed to decide the halting problem of a' Turing machine on larger 
 and larger inputs. The combinational complexity of initial portions of a binary 
 language is related to the amount of oracle necessary to recognize the language. 
 Complete problems for PSPACE, NP, P, and NLOGSPACE relative to arbitrary 
 restricted and unrestricted oracles are presented. Every binary language has a 
 "compressibility", a restriction on oracles which is about as tight as possible 
 while still allowing the language to be accepted. The compressibility of a 
 language is a measure of the complexity of the language which is an alternative to 
 Kolmogorov complexity for finite sequences and to program complexity for finite 
 functions. 
 
 17. Key Words 
 
 Oracles, computational complexity, hierarchies of languages, circuit complexity, 
 complete problems, halting problem. 
 
 7b. Identifiers/Open-Ended Terms 
 
 7e. COSATI Field/Group 
 
 8. Availability Statement 
 
 ORM NTIS-35 ( 10-70) 
 
 19. Security Class (This 
 Report) 
 
 UNCLASSIFIED 
 
 20. Security Class (This 
 
 Page 
 UNCLASSIFIED 
 
 21. No. of Pages 
 
 22. Price 
 
 USCOMM-DC 40329-P71 
 
M/1Y2 3 
 
AUG 2 9 1 ?8»