TheoryComput. Systems30, 165-180 (1997)
Theory of Computing Systems © 1997 Springer-Verlag New York Inc.
Helping by Unambiguous Computation and Probabilistic Computation E Cintioli 1 and R. Silvestri 2 IDipartimento di Matematica e Fisica, Universitii di Camerino, Via Madonna delle Carceri, 62032 Camerino (MC), Italy 2Dipartimento di Scienze dell'Informazione, Universit~t di Roma "La Sapienza', Via Salaria 113, 1-00198 Roma, Italy
[email protected]
Abstract. Sch6ning [S] introduced a notion of helping and suggested the study of the class Phelp(C) of languages that can be helped by oracles in a given class C. He showed that Phelp(BPP) is included in ZPP. Later, Ko [K] introduced a weaker notion of helping, called one-sided helping, and proved that Pl-n,lp (BPP) is included in R and that UP is included in PI-help(UP). The three inverse inclusions are open problems (see [Hem]). Cai et al. [CHV] constructed a relativized world in which the third open inclusion fails. We show relativized worlds in which all three open inclusions fail in a strong way. In particular, we strengthen the result of Cai et al., showing that Phelp(UP) is not included in Few. This is obtained as a corollary of a general result that gives sufficient conditions, on a relativizable complexity class C, to ensure the relativized separation of Ph~lp(UP) from C. Further separations are also derived. The other two open inclusions are showed to fail strongly by the relativized separation of ZPP from P l-h~lp(AM tq co-AM).
1.
Introduction
Sch6ning [S] proposed a notion of an oracle set helping the computation of a language. He wondered how much human assistance can be useful to a program solving a certain problem. His reflections led him to the basic definition of a robust machine, that is, a deterministic oracle Turing machine that always recognizes the same language, independent of the oracle that is used. The oracle only serves to possibly speed up the computation. Precisely, a language L is said to be recognized in polynomial time with the help of an oracle E if there is a robust machine M recognizing L such that M with
166
E Cintioli and R. Silvestri
oracle E runs in polynomial time. The first basic result obtained by Sch6ning states that the class Phelpof languages recognized in polynomial time with the help of some oracle is equal to NP (3 co-NP. Thus, the helping notion could be used as a tool for studying the area between P and NP (3 co-NP. This raised the natural question of characterizing the class Phelp(C) of languages recognized in polynomial time with the help of some oracle in C, where C is a given class of oracle languages. Along this direction, Sch6ning IS] showed that robust machines helped by oracles in BPP recognize languages in ZPP, that is, Phelp(BPP) C ZPP, leaving open whether or not equality holds. However, that line of study was faced by our limited knowledge about the structure of languages in NPNco-NP. To overcome such difficulty and for studying the notion of helping in a richer environment, Ko [K] introduced a notion of partial helping, called one-sided helping, in which the oracle is requested to speed up the computation only when the input belongs to the language. Ko proved that the class Pl-help of languages recognized in polynomial time with the one-sided help of some oracle is equal to NP. He also showed that the class PI-help(BPP) is included in R and that Pl-help(UP) contains UP. Whether the equalities hold are open problems (see [Hem]). Cai et al. [CHV] constructed a relativized world in which Pl-help(UP) does not equal UP. Our two main results strengthen that and show relativized worlds in which the other open equalities dramatically fail. As a corollary of the first one we obtain that
3H,
phnelp(UPH) ~
Few n.
Since Phelp(UP) _ Pl-help(UP) and UP _ Few, this result strengthens the relativized separation obtained in [CHV]. Our second result shows that 3H,
ZPP n ~ pin_help((AM A co-AM)U).
In particular, this implies the weaker separations ZPP n ~ PHIp(BPPH) and R n P~he|p(BPPH). Our first result is of a rather general nature. It uses a uniform approach to define complexity classes introduced by Bovet et al. [BCS2], and independently by Vereshchagin [V]. By such an approach a class C can be defined by a suitable pair of languages (A, B). Informally, we can say that language A corresponds to the accepting computations of machines of type C, and B corresponds to the rejecting ones. The class defined by (A, B) is denoted C(A, B) (different notations are used in [HLS+], [V], and [Herl]). In [BCS2] and IV] it has been shown that nearly all the introduced complexity classes included between P and PSPACE can be defined by such an approach. This fact along with some results saying that the pair (A, B) can take the place of class C relative to certain questions about the class itself (e.g., Theorem 3.1 below), makes it feasible to state general results that are abstracted from specific classes and only rely on properties of pairs of languages. Results of this kind have been obtained in [BCS 1], [BCS2], [V], [Bo], [Herl], and [Her2]. Along this line, our result gives sufficient conditions on a pair of languages (A, B) to ensure 3H,
P~Ip(UP n) ~ C(A, B) tt,
As an easy corollary we are able to obtain, other than the above mentioned result, the following separation: 3H,
P~elp(UPn) g RP;ff(FewP(nl°g°"'n)n),
Helping by UnambiguousComputationand ProbabilisticComputation
167
where R p. (FewP(n l°g°") n)) is the closure under polynomial-time bounded truth-table reductions of the class of languages accepted by polynomial-time nondeterministic Turing machines with at most n l°g°~'n accepting paths on inputs of length n. With regard to second result, we remark that the proof use a standard diagonalization construction whose correctness is proved by two nice combinatorial arguments which come from the "block sensitivity" technique of Nisan [N] and from a technique independently discovered by several people [BI], [IN], [T], [HH].
2.
Notation
Let E be any finite alphabet with {0, 1} c Z. As usual E* denotes the set of all finite strings on ~. For any string x ~ E*, [xt denotes the length o f x and, for any symbol a ~ E, Ix la is the number of occurrences of symbol a in x. For any 1 < i < Ix I, (x)i is the ith symbol o f x . For any languages E, F, IIEII is the cardinality of E, E (9 F := {0x I x ~ E} U {Ix I x ~ F} is the disjoint union of E and F, and E A F := (E - F) t.J (E - F) is the symmetric difference between E and F. We identify every language L with its characteristic function, that is, L(x) = 1 if x e L and L(x) = 0 if x i / L , for every string x. We refer to two nonempty and disjoint languages A, B as a pair of languages and denote it by (A, B). We use two fixed polynomial-time computable and invertible functions (., .): Z* × Z* --~ E* and (.,.,.): Z* x Z* x Z* ~ Z*. We assume familiarity with standard complexity theory notations and complexity classes (e.g., see [BDGI], [BDG2], and [BC]).
3.
Helping and Unambiguous Computation
Our definition of the notions of helping and one-sided helping is formally different from the usual one [S], [K] so that it focus on the language which is helped rather than on the language that helps. Of course, the notions in themselves remain equal to the usual ones.
Definition 3.1. 1. A robust machine is a deterministic oracle Turing machine M such that, for every oracle E, Me(x) halts for all inputs x and L(M E) = L(M~). 2. A language L is recognized in polynomial time with the help (one-sided help) of oracle E if there exists a robust machine M and a polynomial p such that L ( M e) = L and Me(x) halts in p(lxl) steps for all inputs x (x c L). 3. For each class of languages C, let Phelp(C) (Pl-help(C)) be the class of languages recognized in polynomial time with the help (one-sided help) of some oracle in C. We show a general result that gives sufficient conditions, on a relativizable complexity class C, to ensure the existence of an oracle H separating P~elp(UP n) from C H. Recall that UP, unambiguous polynomial time, is the class of languages accepted by nonde-
168
E Cintioli and R. Silvestri
terministic polynomial-time Turing machines that have at most one accepting path. In order to state those sufficient conditions formally, we use the framework of [BCS2] and [V]. By the next definitions we introduce the necessary machinery, essentially following the notations of [BCS2].
Definition 3.2. 1. A function r: E* ~ E* is polynomially bit-computable with oracle E if there exist two functions f and g such that both are polynomial-time computable with oracle E, f is E-valued, and, for every string x, r ( x ) = f ( x , l ) f ( x , 2 ) . . .
f ( x , g(x)). 2. Let (A, B) be a pair of languages. For any oracle E, we denote by C(A, B) e the class of all the languages L for which there exists a function r polynomially bit-computable with oracle E such that, for every string x, x ~ L
¢~
r(x) ~ A
and
x ~ L
¢:~
r ( x ) E B.
In [BCS2] and [V] most complexity classes included between P and PSPACE have been characterized by pairs of languages. For instance, letting Atlp = {0}* 1{0}* and Btle = {0}*, it is easy to see that C(Aup, Bue) E = UP E for all oracles E. In order to prove our result we need a basic tool developed in [BCS2] and [V] for obtaining relativized separations among complexity classes defined by pairs of languages. Such a tool uses a new type of reducibility between pairs of languages, the polylogarithmic-time bit-reduction. Definition 3.3. A pair of languages (A, B) is polylogarithmic-time bit-reducible to a pair (A', B'), (A, B)
x~A
¢~
f(x, 1)f(x,2)...f(x,g(x))~A'
xEB
¢~
f(x, l)f(x,2)...f(x,g(x))EB'.
and
T h e o r e m 3.1 [BCS2], [V].
Let (A, B) and (A', B') be any two pairs of languages,
then (3E)[C(A, B) E ~ C(A', B') e]
¢~
(A, B) :~Pmt (A', B').
To apply this result to our case, we need to find a pair of languages (Aphu, BphU) that characterizes Phelp(UP), that is, C(Aphu, Bphu) E ~ PEelp(UPE) for all oracles E. For the sake of simplicity, we use the alphabet {0, 1, I~}.Let t be a complete and ordered binary tree whose inner nodes are labeled by strings in A v e t3 Bye, all of the same length 2 (depth°ft), and whose leaves are labeled by symbols in {0, 1, I~}. We call such a tree t a I A function is polylogarithmic-time computable if it can be computed in polylogarithmic time by a deterministic Turing machine that has an additional tape on which the machine can write down an index i and then receive the ith symbol of the input string. If i is greater than the length of the input string, the machine receives a special symbol.
Helping by UnambiguousComputation and Probabilistic Computation
......
j'
7°
169
°°
00000000 00000100 01000000 00100000 000000000000000000000000 11~1~1~ Fig. 1. A helping tree of depth 3 and its encoding. helping tree. For any helping tree t there is a special path, that we call the correct path of t, defined as follows: starting from the root, at any node n we go to its left son if the label o f n is in Bue and we go to its right son if the label is in A v e . Any helping tree t can be encoded by a string x = Z l Z 2 . . . Z 2 h _ l Y l Y 2 . . . y 2 ~ where h is the depth of t, strings zi are the labels of the inner nodes (all of length h), symbols Yi are the labels of the leaves, and all the labels are concatenated by the order of a breadth-first search (see Figure 1). At this point we can define the pair (Aphu, Behu): Aphtj ---- {x Ix encodes a helping tree t whose leaf's labels are in {1, ~} and the label of the leaf of the correct path of t is 1 } and Bphu = {x I x encodes a helping tree t whose leaf's labels are in {0, ~} and the label of the leaf of the correct path of t is 0}. It is not hard to see that, for every oracle E, C(Aphu, Behu) E = P~elp(UPe). Now we can state the main result of this section. T h e o r e m 3.2.
Let (A, B) be a pair o f languages A, B c {0, 1, ~}* such that
(i) There is a function b such that, f o r all n, b(n) < logl°g'(l°gn)(n) a.e. f o r some c, and, f o r every z E A U B, Iz[t < b(izl). (ii) For all z ~ A and z' ~ B with Izl = Iz'l, there exists i < Izl such that one and only one of the symbols (z)i and (z')i is 1. Then there exists an oracle H such that P~Ip(UP H) ~ C(A, B) u. Proof. By Theorem 3.1, it suffices to show that (Aphu, BphU) ~pl (A, B). Suppose the contrary, then there are two polylogarithmic-time computable functions f , g, where f is {0, 1, ~}-valued, such that, for every x ~ {0, 1, ~}*, X C AphU
~
f(x, 1)... f(x, g(x)) C A
170
E Cintioli and R. Silvestri
and x E Bphu
¢:~
f ( x , 1 ) . . . f ( x , g ( x ) ) E B.
Functions f and g define a polylogarithmic bit-computable function a by tr(x) = f ( x , 1 ) - . . f ( x , g ( x ) ) , for every x. We are going to show that any such tr cannot respect condition (i), that is, there exists a string x, encoding a helping tree, such that cr(x) has too many symbols 1. We need some notations. Let R and T be two polylogarithmic-time Turing machines that compute functions f and g, respectively. Let q be a polynomial such that, for every x, q (log Ix I) bounds the running time of T (x) and R (x, u) for any u < T (x). For any string x such that Jxl = 2 2h for some h, let n o d e s ( x ) be the prefix o f x of length 2 2h - - 2 h and let l e a v e s ( x ) be the suffix o f x of length 2 h. Note that i f x = Zl • • • Z2h-lyl " " " Y2h encodes a helping tree, then n o d e s ( x ) = zl • • • z2h-t and l e a v e s ( x ) = Yl • • • Y2h• Let x be a string; any integer s with 1 < s < Ix I is a p o s i t i o n o f x . Let x encode a helping tree and let s be a position of l e a v e s ( x ) . We say that a triple (x, u, s) is active if R ( x , u) reads either 1 or 0 in position s o f l e a v e s ( x ) and outputs 1. Observe that i f x and x' are two strings such that X E AphU, X' E B e h u , n o d e s ( x ) = n o d e s ( x ' ) , l e a v e s ( x ) = ~.~-l l [ i ~ - s ,
leaves(x') =
~I'~-10~x'/i~TT-s, and T ( x ) does not read position s of l e a v e s ( x ) , then there exists an index u such that either (x, u, s) or (x', u, s) is active. In fact, a ( x ) ~ A, cr(x') ~ B, and Itr(x)l ---- Icr(x')l, thus, by condition (ii), there exists an index u such that one and only one of the symbols (~r (x)), and (tr (x'))u is 1. We exploit this property of strings like x and x', along with the "smallness" of the set of positions read by machines R and T, to construct a sequence of active triples (xi, Ul, sl) . . . . . (Xm, u,,, Sm) with sl < ' "" < sin, such that, for every k < m, R ( n o d e s ( x m ) leaves(xk), uk) outputs 1 and it does not read positions Sk+l . . . . . Sm of leaves(xk). After this first stage, which we call Generation, we do the second stage, called Elimination, in which some triples are removed from the previous sequence so that the remaining subsequence (xj,, u j,, sj,) . . . . . (Xy~, Ujr , Sir ), with sj~ < . . . < Sir and j~ = m, is such that R ( n o d e s ( x m ) leaves(xj~), uj~) does not read positions sj~ . . . . . sj,_,, sj,+, . . . . . sj~ of leaves(xj,). This allows us to find a string ~ that contradicts condition (i). Let n be an integer such that n = 2 2h, for some h, and so large that x/-~/4q (log n) 2 > b(2 q(l°gn)) (observe that such an n always exists since by condition (i) b(2 qO°gn)) < q (log n)l°g"(q(l°gn))). L e t m = vCn/2q (log n).
Begin Generation Step 0: Set U0 : = ~, x0 : = 0 n - ' / ~ 4-~, and Q0 : = {s [ s is a position of x0 read by T(x0)} U {n - x/~ + l}. StepO < k < m: Letsk b e t h e l e f t m o s t p o s i t i o n o f l e a v e s ( x k _ l ) s u c h t h a t n - v / - ~ + s k Qk-l- L e t x be the string such that Ixl = n, l e a v e s ( x ) = ~sk-t l ~ - s ~ , and n o d e s ( x ) is obtained from nodes(xk_ 5) changing some symbols, whose positions do not belong to Q k - l , from 0 to 1 to make the correct path of x equal to the path of leaf sk. z Let x' be 2 Note that this is always possible since the correct path of xk-1 corresponds to leaf s k - I (So = 1) and S k - I < Sk.
Helping by UnambiguousComputationand ProbabilisticComputation
171
such that Ix'l = n, leaves(x') = I~sk-10~4~-s~ , and nodes(x') = nodes(x). By the above argument, there exists an index uk such that (xk, uk, sk) is active, where xk is either x or x'. Set Uk : = Uk-l U {(Xk, Uk, Sk)} and Qk : = Qk-1 tO {s I s is a position Of Xk read by either R(xk, uk) or R(nodes(xk)~ ~ , Uk)}.
End Generation Note that sl < s2 < • • -
R(nodes(xm) leaves(xk), uk) = R(Xk, uk) -----1.
Begin Elimination Step 0:
Set .A0 : = 0 and V0 : = Urn.
Step k > 0:
If Vk-I = 0, then stop. Otherwise, let j be the m a x i m u m integer such that (Xj, Uj, Sj) is in Vk-l. Set Vk : = Vk-i - {(xi, tli, Si) E Vk_llR(nodes(xm)leaves(xj), uj) reads position si ofleaves(xj)}. Set .Ak : = .Ak-i to {(xj, uj, sj)}.
End Elimination Let r be the n u m b e r of steps done in the Elimination stage. Let A r = { (xjl, Ujl, Sjl), .... (Xjr, Ujr, Sir)} with sj~ < "'" < sj . Note that jr = m. For any i = 1. . . . . r let ai be the symbol in position sj, of leaves(xji). Without loss of generality we can assume that there are at least r/2 indices i such that ai = 1. Let $ be the string such that nodes(Y) = nodes(xm) and leaves(Y) = ~t, l~t~l . . . tit~l~,/'~--Sjr where tl = sj, -- 1 and ti+t =sji+,-sj~ - 1, f o r i = 1. . . . r - 1. C l a i m 1.
There are at least r /2 indices i such that R (£, uj~) = 1.
Proof of Claim 1.
Recall that at the end of the Generation stage, R (nodes(xm) leaves(xk), u~) = 1 for every k _< m, and thus R(nodes(Y) leaves(xj~), uj,) = 1 for i = 1. . . . . r. The Generation stage ensures that R (nodes(Y) leaves(xj,), uj,) does not read positions sj,+, . . . . . sir of leaves(xji), moreover, the Elimination stage ensures that it does not read positions sj, . . . . . sj,_,. If i is an index such that ai = 1, then leaves(xj,) is equal to leaves(Y) on all the positions different from sj, . . . . . sj,_,, sj,+, . . . . . sj. It follows that
R(nodes(Y) leaves(Y), uji) ---~ R(nodes(£) leaves(xj~), uji) = 1.
[]
At the end of the Generation stage we have ~/-~/2q (log n) active triples. At any step k of the Elimination stage, at most q (log n) triples are removed from Vk-j. This means that r >_ (~/-ff/2q(logn)) • (1/q(logn)). It follows that Icr(Y)ll > r/2 > b(2 q~l°gn)) > b (Ity (Y) l) contradicting condition (i). [] Theorem 3.2 allows us to prove relativized separations which give some evidence that Phelp(UP) is not included in some classes that are believed to be more powerful than
172
E Cintioliand R. Silvestri
UP. At least, they say that, even if Phelp(UP) is included in such classes, this cannot be proved by relativizing proof techniques, that is, more specialized and difficult techniques are required. The first of such classes is the class Few, introduced in [CH], which is a generalization of the class FewP of languages accepted by polynomial-time nondeterrninistic Turing machines with at most polynomially many accepting paths. It holds that UP _c FewP _c Few, moreover, as has been shown in [CH], Few contains the boolean closure of FewP. The second class concerns a different generalization of FewP in that we allow more accepting paths. Precisely, given a function t (n) let FewP(t (n)) be the class of languages accepted by polynomial-time nondeterministic Turing machines with at most t (n) accepting paths on inputs of length n. If 7- is a class of functions, then let FewP(7-) = [-.Jt~7-FewP(t(n)). Note that FewP(1) --- UP, FewP(n °d)) = FewP, and FewP(2 n°+) = NP. Thus, FewP(n l°g°+n) is an intermediate class between FewP and NP. Corollary 3.1. (a) There exists an oracle H such that Phnelp(UPt4) ~ Few H. (b) There exists an oracle H such that PHIp(UpH ) ~ FewP(n l°g°m n)H. Proof.
(a) Let
AFew = {zy • {0, 11" I Izl = rlog(ly])] A lYll < [-log(ly])] m (Z)lylt+l = 1}
and let BFew = {zy • {0, 1}* [Izl = [log(lyl)] A lYll < [log(lYl)]
m (Z)lyh+ 1 =
0}.
Then it is easy to see that Few e = C(AFew, BFew)e for all oracles E. Moreover, (AFew, BFew) satisfies conditions (i) and (ii) of Theorem 3.2. (b) Let h be an integer constant, define Ah • {z • {0, 1}* I Izll --< logl°gh(l°g(Izl))(lzl) A IZ[l > 0}
and Bh ----{Z • {0, 1}*I[ZIl =0}-
It is possible to verify that FewP(n t°g°<~'n)e = Uh C(Ah, Bh) E for all oracles E. It is also clear that ( A h , B h ) satisfies the conditions of Theorem 3.2. [] Observe that from the above corollary we obtain that there exist relativized worlds in which Ph~lp(Few) ~; Few and Phelp(FewP) ~ FewP. Other applications of Theorem 3.2 concern closures of the above classes with respect to some polynomial reducibilities. We consider the polynomial-time bounded truth-table reducibility <~tt and a type of positive reducibility, introduced by Hemachandra and Jain [HJ], defined as follows: L -epos
Helping by Unambiguous Computation and Probabilistic Computation
173
Corollary 3.2. p,n (a) There exists an oracle H such that P~Ip(UP/4) ~ Rbt t (FewP(n l°go~l)n)tt). (b) There exists an oracle H such that RePp~(UP H) g R~;t~(FewP(n'°g°">")n). (c) There exists an oracle H such that (NP (q co-NP) H ~ Rp;H (FewP(nl°g°<" n) n). Proof (a) Let d: {0, 1}* ~ N be the function such that, for every x E {0, 1}*, d ( x ) is obtained by adding 1 to the integer whose binary numeral is x, for instance, d(0 n) = 1 and d(1 n) --- 2 n. Let h and k be two integer constants, define Ah,k ~- {Z E {0, 1}* I 3v, Yl . . . . . Yk : z = vyl • " Yk A Ivl = 2 k A [YI[ . . . . =
lYkl A y~ . . . . . Yk E. Ah I...IBh A (O)d(a) = 1
where a
= Ah(yl)'"
Ah(Yk)}
and Bh,k :
{Z E {0, l}* I 313, Yt . . . . .
Yk : Z = Vyl "'" Yk A
= lYkl A Yl . . . . . Yk E Ah U Bh where a
= Ah(Yl)""
A (l))d(a) :
Ivl
:
2k m
lyll
....
0
Ah(Yk)},
where (Ah, Bh) is the pair of languages defined in the proof of Corollary 3.1. It can be verified that RbPtte(FewP(n l°g°~"n)e) = [,-Jh,kC(Ah,k, Bh,k)E for all oracles E. Moreover, (Ah,k, Bh,k) satisfies the conditions of Theorem 3.2. (b) It derives from the fact, proved in [CHV], that Pl-help(UP) = RPpos(UP) and from (a). (c) It follows from (a) and the well-known fact that Phdp(UP) C_ NP A co-NP. []
4.
Helping and Probabilistic Computation
In this section we show a relativized separation of the probabilistic class ZPP from Pl-help (AMOco-AM), which in turn implies relativized separations of ZPP from Phelp(BPP) and of R from Pl-help(BPP). These last two relativized separations indicate that proving either ZPP c Phelp(BPP) or R c Pl-help(BPP), if possible at all, is very difficult in that it would require proof techniques that do not relativize. First, we give the definition of the Arthur-Merlin game class AM which was introduced in [Bab].
Definition 4.1. 1. For any oracle machine Q, polynomial p, string z, and oracle E, let p ( Q E , p, z) =
Pr
(3y : lY[ = p(Izl) A Q e ( ( z , r, y)) accepts).
r: Irl=P(Izl)
2. Let E be any oracle set. AM e is the class of all languages L for which there exist a polynomial-time deterministic oracle Turing machine Q and a polynomial p such that, for every string x, x ~ L
¢~
p ( Q e , p , x ) > 32
and
x ~ L
¢~
1 p ( Q E , p , x ) < 3"
174
P. Cintioli and R. Silvestri
It is known that AM includes NP U BPP, thus AM n co-AM includes both BPP and NP O co-NP (indeed it includes (NP N co-NP)BPP). The following result obtained in [Bal] gives us a convenient way for "enumerating the machines" of Pl-hCJp(AM n co-AM) on which we are going to diagonalize. T h e o r e m 4.1 [Bali. Let C be any relativizable class of languages and let E be any oracle set. A language L belongs to P~_help(Ce) if and only if there exist two languages D and B, a function f , and a polynomial p such that:
(i) B ~ p E , D ~ C E, (ii) function f can be computed in polynomial time with oracle E ~ D, (iii) for every string x, x ~ L ¢> (3y)[[yl < p(Ixl) A (x, y) ~ B], and (iv) for every string x, x E L ~ (x, f ( x ) ) E B. The proof of the following result uses a standard diagonalization whose critical core consists of two nontrivial combinatorial arguments. Theorem 4.2.
There exists an oracle H such that
ZPP H g P~help((AM n co-AM)H). Proof Let {Mi, Pi}i be an enumeration of all the pairs consisting of a polynomialtime clocked deterministic oracle Turing machine Mi and a polynomial Pi. Let {Tj }j be an enumeration of polynomial-time clocked deterministic oracle transducers. Let { Qh, Qh, Ph }h be an enumeration of all the triples consisting of a pair of polynomialtime clocked deterministic oracle Turing machines Qh and Qh, and a polynomial Ph. We introduce the following notations. We say that QhE, QhE, and z agree with AM N co-AM if (P(QhE, Ph, Z) > 32 m P ( 0 ~ , Ph, Z) < ½) -E
2
v ( P ( Q ~ , Ph, z) < ½ A P ( Q h , Ph, Z) > 3)" For any ah and for any oracle E, l e t A ( Q ~ ) = {zl P(Qh,E Ph, Z) > ~}. Note that if OhE, QhE, and z agree with AM N co-AM for all strings z, then A ( Q ~ ) ~ (AM N co-AM) e. From Theorem 4.1 it derives that, for any oracle E and for any language L, L c P~_help((AM n co-AM) E) iff there exist indices i, j, and h of the above enumerations, such that, for every string x, (a) x c L 4:> (~Y)[lYl < pi(lx[) A M/E((x, y)) accepts], (b) QhE, QhE, and x agree with AM N co-AM, and ,rE~A(Q E) . . . . (c) x E L ~:~ Mi~((x, ~j tx))) accepts. For every oracle E, let L ( E ) = {x I (Sy)[ly] = Ix l A y c E n 1Z*]}. We construct by steps an oracle H such that L ( H ) ~ ZPP n - P~help((AM O co-AM)n). We start our construction with H0 = 0E* and at each step k, for a sufficiently large m, we remove from Hk-i all the strings in 0E "-1 and add at least 2 " / 4 strings belonging to either 0E m-l or 1E .... 1. Thus, for a l l n , I I H N E " l J __> 2 n / 4 a n d e i t h e r H N 1Z n-I = 0 o r H N 0 E n-I = 0. For such an oracle H, it is easy to see that L ( H ) ~ ZPP H. On the other hand, for proving that L ( H ) q[ PHhelp((AM n co-AM)H), oracle H will be constructed
Helping by Unambiguous Computation and Probabilistic Computation
175
in such a way that at any step at least one of the three conditions (a), (b), or (c) fails. Standard techniques as those of Rackoff [R] (see also [BDG2]) about "critical strings" do not work here because we have to add, at any step, too many strings to the oracle. To overcome this difficulty we use the "block sensitivity" technique of Nisan [N].
Begin construction
Step 0:
Let H0 := 0~*.
Step k = (i, j, h):
Let q be a polynomial such that, for every n, q(n) bounds, for all oracles E, the running time of the following computations: TjE (0 ~), Mfi ((0 n , y)) for all y with lYl < pi(n), and QhE ((z, r, y)), O.~((z, r, y)) for all z, r, and y such that Izl = n and Ir l, lYl = Ph(n). Choose an integer m so large that it is greater than the lengths of all the strings queried by the computations involved in the previous steps and that it satisfies 1000q (m)q (q (m)) 4 < 2m/4. For the sake of convenience we introduce the following notations. Let H ' = Hk-i - - 0 ) " ] ~ m - 1 and 7 - / = {SI (S _c 0 E m-l v S _ 1 E r a - l ) A IISII _> 2m/4}. We distinguish three cases. Case 1. Condition (a) can be negated, that is, there exists a set S 6 7-/such that (S _ 1E rn-I mVy [yl < pi(m) M/M'us((0 m, y)) rejects) v (S __. 0• m-I A ^
3y : lYl < pi(m) MiH'uS((om, y)) accepts). SetHk := H ' U S . Case 2. Condition (b) can be negated, that is, there exist a set S E 7-/and a string with I~1 <- q(m) such that QhH'u$, {~ff'u3, and ~ do not agree with AM n co-AM. SetH~ := H ' U S . Case 3. Both cases 1 and 2 fail. Then find a set S E 7-[ such that S ___ 1 E " - l and M~ 'u3 (lOm Tj(H'U~)~A(onh'U~) (0m))) rejects (in this way, condition (c) is negated). SetHk := H ' U S . ,
E n d construction Set H := limk Hk. It is easy to see that if, at every step, one of the three cases can be satisfied, then oracle H separates ZPP from Pl-help(AM N co-AM). Consider the above construction at step k = (i, j, k). Let q, m, 7-(, and H ' be as they are defined at that step. To show that at least one of the three cases can be satisfied, it suffices proving that if cases 1 and 2 fail, then case 3 can be satisfied. Therefore, in the following, we suppose that cases 1 and 2 fail. Since case 1 fails, for every S ~ 7-/ and y with lyt < pi(m), if computation Min'us((o m, y)) accepts, then it queries at least one string belonging to S. For, if not, there exist S E 7-/and 7 with lT I < pi (m) such that computation Mff'us((0 m, 7)) accepts and all the strings queried do not belong to S. Then there is a set S such that S 6 7-/, _c 0 Z m-l, and that does not contain any of the string queried. Thus M/n'us((0 m, 7)) accepts, contradicting the assumption that case 1 fails.
176
P. Cintioli and R. Silvestri
Consider the polynomial-time transducer T defined as follows. T ° e e on input x -¢ 0 m outputs a fixed string. T ° e e on input 0 m simulates computation ~DeE(0m) computing its output y. Successively, it simulates M/° on input (0 m, y), if this computation queries a string of length m receiving answer " y e s " then transducer T outputs this string, otherwise it outputs a fixed string. The main feature o f T is that, for every S ~ 7-/, if M~'US((0 m, Tj(H'US)eA(Q~'US)(om))) a c c e p t s , then the output o f T(n'us)@a(Q~'US)(om) belongs to S. Thus, in order to show that case 3 can be satisfied, it suffices to prove that there is a set S such that S c 7-L S c 1~] m - I , and the output o f T(H'US)@A(Q~'US)(om) does not belong to S. Before we can proceed proving that, we need to introduce some definitions. For any pair of disjoint sets Y, N c l~Z m-1 and for any S ~ 7-[ we say that S is compatible with (Y, N) if Y _ S and N n S = 13. Moreover, we say that (Y, N) is a 1-certificate (O-certificate) for a string z if, for every set S ~ 7-[ such that S c 1E m-1 and S is compatible with (Y, N), it holds that p(Q~'US, Ph, Z) > 2 (p(Q~'US, Ph, Z) < 1). We say that (Y, N) is a certificate for z if (Y, N) is either a 1-certificate or a 0-certificate for z.
For any string z with [zl _< q(m) and for any set S ~ 7-[ with S c 1 Z m-I there exists a certificate (Y, N) for z such that S is compatible with (Y, N) and IIYUNII _< Claim 1.
18q(Izl) 2.
Proof of Claim 1.
The proof uses the "block sensitivity" technique ofNisan [N, Lemma 2.4] (see also Theorem 3.1 of [IN]). Let z be any string such that Izl _< q(m). We need some notations. Let 7-/1 (resp. H0) be the subset of H of all the sets S such that S -c 1E m-I and p(Ql~'us, Ph, Z) > 2 3 (resp. p(Q~4'vs Ph, z) < ½). Note that, since case 2 fails, for any set S ~ 7-/either ~,~h , Ph, Z) > 2 o r p(Qff'us, Ph, Z) < 3" 1 For any D c _ l ~ m - I a n d S E 7-/1 U "7-/0 prr~t-l'US we say that S is sensitive to D if S c 7-/1 :=~ S A D ~ 7-/0 and S c ~ 0 =~ S A D ~ ~ j . The block sensitivity of S is the maximum b so that there exist disjoint sets DI . . . . . Ob 1E m-I such that S is sensitive to Di for all i = 1. . . . . b. We denote by bs the maximum over all S ~ 7-/1 U 7-/0 of the block sensitivit_y of S. First we show that bs < 3q([z]). Let S be a set such that the block sensitivity of is equal to bs, and let b t . . . . . Dbs _C 1~; m-1 be bs disjoint sets such that S is sensitive to /)i for all i = 1 . . . . . bs. Suppose that S ~ 7-/1. Then ,~ A/9i ~ 7-(0 for all i = 1. . . . . bs. Let {rj . . . . . re} be the set {r [ Irl ---- Ph(lzl) A (3y : [Yl ---- Ph(lZl) A Qff'uS((z, r, y)) accepts)}. For each rt choose a string Yt such that Q~ruS((z, rt, yt)) accepts. Since p(Q~/'u~, Ph, Z) > ~2 and e ( Q h H'u3Ab~ , Ph, Z) < ~I for all i = 1, . . . . bs, 1 it must be the case that, for any i = 1. . . . . bs, there are at least ge indices t ..-~H'USAb; ,,
{1 . . . . . £} such that ~,~h
t~Z,
..-~H'U~SAL)i , ,
rt, Yt)) rejects. If ~,~h
t~Z, rt, Yt)) rejects, then,
since Qhn'U3((z, rt, Yt)) accepts, the computation Q~/'u3((z, rt, yt)) have to make at least one query in /)i. Thus, the total number of strings queried by all the computa~ tions Ql~'US((z, rt, yt)), for t E {1 . . . . . £}, and belonging t o / ) l U . . . U/)bs is greater than lebs (recall that/)1 . . . . . /gbs are disjoint sets). Moreover, since the polynomial q bounds the running time of Oh, it holds that the total number of strings queried by all
Helping by Unambiguous Computation and Probabilistic Computation
177
the computations Qtff'uS((z, rt, yt)), for t 6 {1 . . . . . e}, is less than £q(Iz[). It follows that ½ebs _< eq(Izl), thus bs < 3q(Izl). If S 6 ~ 0 we can prove the same by applying the above argument to Qh instead of Qh. Let S be any set in 7-[1 U 7%. We say that D is a minimal block for S if S is sensitive to D, but to no proper subset o f D. Note that any set D, to which S is sensitive, contains some minimal block for S. We claim that the cardinality o f any minimal block is no more than 2bs. To show that, consider a minimal block D for S. Firstly, we observe that, for any nonempty and proper subset D ' o f D, if (S A D) A D ' ~ 7-/1 U ~ 0 , then S / x D is sensitive to D'; for otherwise S would be sensitive to D - D', contradicting that D is a minimal block for S. Now, if l I S A DII > 2m/4, then any element w of D is such that (S A D) ,6 {w} ~ ~ t U 7-t0 and thus S A D is sensitive to {w}; it follows that IIDII ~ bs. On the other hand, if l I S A OlI = 2m/4, then it must be the case that liD - all _< IID n SII, thus we can make a partition Dl . . . . . Ot of D such that, for any i = 1 . . . . . t, IIDi II < 2 and if Di contains an element of D - S, then it also contains an element of D n S. Clearly, (S A D) A Di E 7-/1 U 7-~0 for every i = 1. . . . . t. It follows that IIDII < 2t < 2bs. Now, let DI . . . . . Db be a maximal collection o f disjoint minimal blocks for S. Let Y = (Dr U . . . U Db) N S and let N = (Dr U . . . U Db) -- S. We claim that (Y, N ) is a certificate for z. For otherwise there is a set S' E ~ l U 7-(0 compatible with (Y, N ) such thatS~l =~ S ' ~ 0 a n d S E 7 - t 0 =¢,S'E~1.LetE=SAS'.SinceSAE=S', it holds that S is sensitive to E; hence E contains a minimal block E ' for S. E ' is disjoint from D1 U • - • U Db contradicting the maximality o f the collection Di . . . . . Db. S i n c e b < bs, IlDill < 2 b s f o r a l l i = 1 . . . . . b, and Y U N = Dl U . . . U D b , We can conclude that (Y, N) is a certificate for z such that S is compatible with (Y, N) and IIY U NIl < 2bs 2 < 18q(Izl) z. []
For any string z with Izl ~ q(m) there exists a set N cc_ 1~am - I such that (0, N) is a certificate for z and IINII _ (18q(q(m))2) 2.
C l a i m 2.
Proof of Claim 2. The proof of this claim is based on an argument extensively used in the literature (Lemma 2.2 in [BI], see also [IN], IT], [HH], [BCS1], and [Y]). Let z be any string such that Izl 5_ q(m). Let r = 18q(Izl) z. Consider the following procedure. Let So : = 1E m-I and let a : = 0. Repeat the following 2r times. Let a : = a + 1. Choose a certificate (Ya, Na) for z such that Sa-t is compatible with (Ya, Na) and IIYa U Na II - r, and choose a set Sa such that Sa ~ 7-[, Sa ~ 1~] m - l , and San (Y1 U N 1 U . . . U Ya U Na) = 0. Note that, according to Claim 1, a certificate (Y~, N~) with the above properties can always be found. Also, for any a = 1 . . . . . 2r, a set S~ can be found, because 2r • r < 2(18q(q(m))2) s < 2m/4. A m o n g the 2r certificates for z, (Yt, N1) . . . . . (Y2r, N2r), there are at least r, (Ya,, N~,) . . . . . (Ya,, Na,) with I < al < " " < ar ~ 2r, such that either they are all 1-certificates or they are all 0-certificates. Without loss of generality we can assume that they are 1-certificates. Let 7-/t (resp. ~ 0 ) be the subset o f 7-/of all the sets S such that S ___ 1E m-1 and p(Qff'us, Ph, Z) > 32 (resp. p(Qff'us, ph, z) < ½). We distinguish
178
P. Cintioli and R. Silvestri
two cases: 1. v S e 7-to: s n (Y~, U Na, U . . . U Y.r U Nar) ~ 13. Let N = Ya, U Na, U . . . U Yar U Nar. We claim that (13, N) is a certificate for z. In fact, since ¥S 6 ~ o S n N ~ 0, if S is any set that is compatible with (0, N) and that belongs to 7-/1 U ~0, then S e 7-/1. Moreover, IINI] _< r 2 _< (18q(q(m))2) 2. . 3 S E 7-[0: S ("1 (Eat U N a 2 U . . . U Ya~ to N a t ) = 0. Let S be a set such that S ~ 7% and S fq (Ya~ UN,~ U " " tO Ya, tO Na,) = 0. From Claim 1 we know there is a 0-certificate (Y, N) for z such that S is compatible with (I7,/~/) and 1117U -~ll _< r. Observe that, for any i = 1. . . . . r, there cannot exist a set in ~1 U 7-/0 that is compatible with both (Ya,, ga,) and (Y, N). This implies that either 17 fq Na, 5~ 0 or N A Y,, ¢ 13. Since S ¢q (Y,, to Na,) = 13 and is compatible with (17, N), it cannot happen that 17 A N,, ¢ 0, thus N N Y,, ~ 0. Now, we claim that the sets Y,, . . . . . Ya. are pairwise disjoint. Let ai < aj, from the procedure above, it derives that Saj-1 is compatible with (Y,j, Na~) and that Saj-l f) (Y,, to N,,) = 0. It follows that Yaj C Sa~-l and S,~-1 (q Ya, = 0, thus Y,j and Y,~ are disjoint. Since .~ A Y,, ~ 13 for all i = 1. . . . . r, it holds that [INI[ _> r, but III7 U ~'[I < r, for which it must be the case that 17 = 0. It follows that (0,/V) is a certificate for z with IINII < 18q(lzl) 2. [] Consider the tree of all the computations o f machine T on input 0 ~ and oracle H ' ~ E as oracle E varies. This is a binary tree whose inner nodes are labeled by the queries that machine T makes to oracle E. If a node has label z, then its left son corresponds to the computation in which query z receives answer "no" and its right son corresponds to the one in which query z receives answer "yes." The leaves are labeled by the strings of the output. Thus any path of this tree corresponds to a computation of machine T on input 0 m and oracle H ' ~ E for a suitable oracle E. By Claim 2 we can associate to every inner label z of the tree a set N ( z ) such that (13, N ( z ) ) is a certificate for z and PIN(z)tl _< (18q(q(m))2) 2. In this way, we also associate to every z an answer which is "yes" if (13, N ( z ) ) is a 1-certificate, and it is "no" otherwise. If we start from the root of the tree and follow the answers associated to the inner labels, we determine a special path. Let z L. . . . . zt be the inner labels and let y be the label o f the leaf o f that path. Let V be the set of all the strings of length m queried to oracle H ' during the computation that corresponds to the special path. We can find a set S such that S c 7-/, S c 1E m-l, and S N ( N ( Z l ) U . . . U N ( z t ) IA V U {y}) = 13 (recall that t < q(m), [[N(zi)][ < (18q (q (m))2) 2, and [IVII _< q (m)). Clearly, computation T (H'U~)~A(Q~'U~;)(0m) is equal to the computation that corresponds to the special path, since S is compatible with
(O,N(zi))fora]li
= 1. . . . .
^ A H'u~ t. I t f o l l o w s that T ( H'U s)~ (Qh ) ( O m ) o u t p u t s y a n d y d o e s
not belong to S. The following corollary is immediate from Theorem 4.2.
Corollary 4.1. (a) There exists an oracle H such that ZPP H ~ P~elp(BPPH). (b) There exists an oracle H such that R H ~ P~help(BPPH). (C) There exists an oracle H such that ZPP ~ ~ P~help((NP n co-NP)H).
[]
Helping by Unambiguous Computation and Probabilistic Computation
5.
179
Open Problems
It does not seem possible to derive from Theorem 3.2 the relativized separation of Phelp(UP) from R p (UP). Since we believe that this can be proved, an interesting problem is to find a generalization of Theorem 3.2 from which it is possible to derive that separation. Along this line, the ultimate goal would be to find conditions on a pair of languages (A, B) that are, other than sufficient, also necessary for the existence of a relativized separation of Phelp(UP) from C(A, B). With regard to Theorem 4.2, observe that if C(A, B) is a class such that NP _ pC(A,B) then ZPP _ Pl-help(C(A, B)) (indeed NP _ Pl-help(C(A, B))). This along with Theorem 4.2 leads us to conjecture that if for every oracle E there exists an oracle H such that NP e~/4 ~ Pc(a'B)e~", then there exists an oracle F such that ZPP F PlF_help( C ( A , B ) F ) .
References [Babl L. Babai, Trading Group Theory for Randomness, Proc. 17th ACM Symposium on Theory of Computing, 1985. DO. 421-429. [Bal] J. L. Balcflzar, Self-Reducibility, Journal of Computer and System Sciences 41 (1990), 367-388. [BC] D. P. Bovet and P. Crescenzi, Introduction to the Theory of Complexity, Prentice-Hall, Englewood Cliffs, NJ, 1994. [BCS 1] D. P. Bovet, P. Crescenzi, and R. Silvestri, Complexity Classes and Sparse Oracles, Proc. 6th Structure in Complexity Theory Conference, 1991, pp. 102-108. Also Journal of Computer and System Sciences 50 (1995), 382-390. [BCS2] D. P. Bovet, P. Crescenzi, and R. Silvestri, A Uniform Approach to Define Complexity Classes, Theoretical Computer Science 104 (1992), 263-283. [BDG1] J. L. Balc~izar, J. Dfaz, and J. Gabarr6, Structural Complexity 1, vol. 1, Springer-Verlag, Berlin, 1988. [BDG2] J. L. Balc~izar, J. Diaz, and J. Gabarr6, Structural Complexity H, vol. 2, Springer-Verlag, Berlin, 1990. IBI] M. Blum and R. Impagliazzo, Generic Oracles and Oracle Classes, Proc. 28th IEEE Symposium on Foundations of Computer Science, 1987, pp. 118-126. [Bol B. Borchert, On the Acceptance Power of Regular Languages, Proc. 1lth Symposium on TheoreticalAspects of Computer Science, Lecture Notes in Computer Science, Vol. 775, Springer-Verlag, Berlin, 1994, pp. 533-541. [CH] J. Cai and L. Hemachandra, On the Power of Parity Polynomial Time, Mathematical Systems Theory 23 (1990), 95-106. [CHV] J. Cai, L. Hemachandra, and J. Visko~, Promises Problems and Access to Unambiguous Computation, Proc. 17th Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 629, Springer-Verlag, Berlin, 1992, pp. 162-171. [Hem] L. Hemachandra, Fault-Tolerance and Complexity, Proc. 20th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, Vol. 700, SpringerVerlag, Berlin, 1993, pp. 189-202. [Herl] U. Hertrampf, Complexity Classes Defined via k-Valued Functions, Proc. 9th Structure in Complexity Theory Conference, 1994, pp. 224-234. [Her2] U. Hertrampf, Complexity Classes with Finite Acceptance Types, Proc. 1 lth Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 775, SpringerVerlag, Berlin, 1994, pp. 543-553. [HH] J. Hartmanis and L. A. Hemachandra, Robust Machines Accept Easy Sets, Theoretical Computer Science 74 (1990), 217-225. [HJ] L. Hemachandra and S. Jain, On the Limitations of Locally Robust Positive Reductions, International Journal of Foundations of Computer Science 2 (1991), 237-255.
180
P. Cintioli and R. Silvestri
[HLS+ ]
[IN] [K] [N] [R] IS] [T] IV] [Y]
U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer, and K. W. Wagner, On the Power of Polynomial Time Bit-Reductions, Proc. 8th Structure in Complexity Theory Conference, 1993, pp. 200-207. R. Impagliazzo and M. Naor, Decision Trees and Downward Closures, Proc. 3rd Structure in Complexity Theory Conference, 1988, pp. 29-38. K. Ko, On Helping by Robust Oracle Machines, Theoretical Computer Science 52 (1987), 15-36. N. Nisan, CREW PRAMs and Decision Trees, SIAM Journal on Computing 20 (1991), 999-1007. C. Rackoff, Relativized Questions Involving Probabilistic Algorithms, Journal of the ACM 29 (1982), 261-268. U. Sch~ning, Robust Algorithms: a Different Approach to Oracles, Theoretical Computer Science 40 (1985), 57-66. G. Tardos, Query Complexity, or Why is it Difficult to Separate NP a O co-NPa from pa by Random Oracles, Combinatorica 9 (1989), 385-392. N.K. Vereshchagin, Relativizable and Nonrelativizable Theorems in the Polynomial Theory of Algorithms, Russian Academy of Sciences. Izvestiya. Mathematics (AMS) 42 (1994), 261-298. T. Yamakami, Structural Properties for Feasibly Computable Classes of'l~pe Two, Mathematical Systems Theory 25 (1992), 177-201.
Received December 1994, and in final form June 1996.
