4.6.4 ANSWERS TO EXERCISES (Web site design and hosting) 639 37. The statement
4.6.4 ANSWERS TO EXERCISES 639 37. The statement is true. The labels in the reduced graph of the binary chain are [TZ/~~] for k = eo, . . . , 0; they are 1, 2, . . . , 2e0, n in the dual graph. [Similarly, the right-to-le% m-ary method of exercise 9 is the dual of the left-to-right method.] 38. 2t are equivalent to the binary chain; it would be 2t-1 if eo = el + 1. The nu ber of chains equivalent to the scheme of Algorithm A is the number of ways to cornT ute the sum of t + 2 numbers of which two are identical. This is fjt+, + +ft, where fm is the number of ways to compute the sum of m + 1 distinct numbers. When we take commutativity into account, we see that fm is 2-m times (m + l)! times the number of binary trees on m nodes, so fm = (2m -1)(2m -3). . . 1. 39. The quantity l([nl, nz,. . . , nm]) is the minimum of arcs -vertices + m taken over all directed graphs having m vertices Sj whose in-degree is zero and one vertex t whose out-degree is zero, where there are exactly nj oriented paths from sj to t for 1 < j 5 m. The quantity l(nl, 722,. . , n,) is the minimum of arcs-vertices+1 taken over all directed graphs having one vertex s whose in-degree is zero and m vertices tj whose out-degree is zero, where there are exactly nJ oriented paths from s to tj for 1 2 j 5 m. These problems are dual to each other, if we change the direction of all the arcs. Note: C. H. Papadimitriou points out that this is a special case of a much more general theorem. Let N = (nij) be an m X p matrix of nonnegative integers having no row or column entirely zero. We can define I(N) to be the minimum number of multiplications needed to compute the set of monomials { z; ~. . . xkrn3 1 1 5 j 5 p}. Now 1(N) is also the minimum of arcs - vertices + m taken over all directed graphs having m vertices si whose in-degree is zero and p vertices t, whose out-degree is zero, where there are exactly nt3 oriented paths from si to t, for each i and j. By duality we have I(N) = l(NT) + m -p. N. Pippenger has proved a comprehensive generalization of the results of exercises 27 and 32. Let L(m, p, n) be the maximum of I(N) taken over all m X p matrices N of nonnegative integers nij 5 n. Then L(m,p, n) = min(m,p)lgn + H/lgH f O(m + p + H(loglogH) /2(logH)-3/2), w h ere H = mpIg(n + 1). [SIAM J. Com- puting 9 (1980), 230-250.1 40. By exercise 33, it suffices to show that l(mlnl $ . . + mtnt) _< l(ml, . . . , mt) + l([nl,. . . , n,]). But this is clear, since we can first form {xml,. . . , rmt} and then compute the monomial (~~l)~l.. . (xmt) +. Notes: Theorem F is a special case of this result, since we clearly have 1(2 , Z) 2 m + V(Z) -1 when X(Z) 2 m. One strong way to state Olivos s theorem is that if a~, . . I a, andbo, . . . . b, are any addition chains, then 1(c cijaib,) < r + s + c ct3 -1 for any (T + 1) X (s + 1) matrix of nonnegative integers Cij. 41. [To appear.] The stated formula can be proved whenever A 2 9m2. Since this is a polynomial in m, and since the problem of finding a minimum vertex cover is NP hard (cf. Section 7.9), the problem of computing l(nl, . . . , n,) is NP complete. [It is unknown whether or not the problem of computing l(n) is NP complete.] SECTION 4.6.4 1. Set y +- x2, then compute (( . . . (~2~+ly $ u~~-l)y + . . . )y + 2~1)~.