Theorem 2.1.There is a zero-error randomized query algorithm solving the AND-OR Tree problem with only O(n.753)queries in expectation. It's not hard to see that the problem is the same as NAND Tree,where each node is the NAND gate. (Verify this yourself.)The algorithm is sometimes called alpha-beta pruning.It's very simple:it recursively runs in a top-down manner.For each gate G,randomly choose one G;of the two children Gi,G2 to evaluate it(recursively).If G;evaluates to 0,then we know that G also evaluates to 1,thus we don't need to compute the other child of G.If G;evaluates to 1,then we have to compute the other child. The algorithm surely has zero error.What's the expected number of queries?Suppose the height of the current subtree is h,and denote the expected time to evaluate the subtree is To,where b is the value that the subtree evaluates to.Then it's not hard to see that To(h)=2T1(h-1)//we have to compute bothchildren (whobothevaluate to 1) T(h)=2To(h-1)+(T(h-1)+To(h-1))=To(h-1)+T1(h-1)//w.p.12,we evaluate only one child. Combining the two relations,we have Ti(h)=%Ti(h-1)+2T1(h-2).Solving this recursion we get T)=(）=(20-=n7- Finally,let's mention that the algorithm is optimum in the sense that any randomized algorithm needs these many queries.If you are indeed interested in more details of the algorithm and its optimality,see paper [SW86]. Example 2.3:Sink problem.This time we are given a directed graph,and we wish to know whether the graph has a"sink"vertex,which has out-degree n-I and in-degree 0.(Namely,everyone else points to it,but it doesn't point to anyone.)What we can ask is for any ordered pair(i j),whether there is an edge from i to j.What's the minimum number of queries we need? References [KN97]Eyal Kushilevitz and Noam Nisan,Communication Complexity,Cambridge University Press,1997.Theorem 2.1. There is a zero-error randomized query algorithm solving the AND-OR Tree problem with only O(n0.753…) queries in expectation. It’s not hard to see that the problem is the same as NAND Tree, where each node is the NAND gate. (Verify this yourself.) The algorithm is sometimes called alpha-beta pruning. It’s very simple: it recursively runs in a top-down manner. For each gate G, randomly choose one Gi of the two children G1, G2 to evaluate it (recursively). If Gi evaluates to 0, then we know that G also evaluates to 1, thus we don’t need to compute the other child of G. If Gi evaluates to 1, then we have to compute the other child. The algorithm surely has zero error. What’s the expected number of queries? Suppose the height of the current subtree is h, and denote the expected time to evaluate the subtree is Tb, where b is the value that the subtree evaluates to. Then it’s not hard to see that T0(h) = 2T1(h-1) // we have to compute both children (who both evaluate to 1) T1(h) = ½ T0(h-1) + ½(T1(h-1)+T0(h-1)) = T0(h-1) + ½ T1(h-1) // w.p. 1/2, we evaluate only one child. Combining the two relations, we have T1(h) = ½ T1(h-1) + 2T1(h-2). Solving this recursion we get T1(h) = ( 1+√33 4 ) ℎ = (2h ) 0.753… = n0.753… Finally, let’s mention that the algorithm is optimum in the sense that any randomized algorithm needs these many queries. If you are indeed interested in more details of the algorithm and its optimality, see paper [SW86]. Example 2.3: Sink problem. This time we are given a directed graph, and we wish to know whether the graph has a “sink” vertex, which has out-degree n-1 and in-degree 0. (Namely, everyone else points to it, but it doesn’t point to anyone.) What we can ask is for any ordered pair (i,j), whether there is an edge from i to j. What’s the minimum number of queries we need? References [KN97] Eyal Kushilevitz and Noam Nisan, Communication Complexity, Cambridge University Press, 1997