Circuit Complexity - Models of Computation: Exploring the Power of Computing - page 451

Hint: Argue that the external path length is minimal for a nearly balanced binary tree.
Use this fact and a proof by induction to obtain the external path length of a binary
tree with L = 2 k for some integer k . Use this result to establish the above statement.
9.5 For positive integers r and s , show that

s/r ( s mod r )+ s/r ( r − s mod r )= s .

Hint: Use the fact that for any real number a ,

a − a = 1if a is not an integer and

r .
9.6 ( Binomial Theorem ) Show that the coefficient of the term x i y n−i

0 otherwise. Also use the fact that s mod r = s

− s/r ·

in the expansion of

is the binomial coefficient i .Thatis, the polynomial ( x + y ) n

n
i

x i y n−i

n

( x + y ) n =

i = 0

2 n

9.7 Show that the following sum is closely approximated by 0 . 4772

·

for large n :

( n/ 2 )+ √ n n

i

i =( n/ 2 )

Hint: Use the fact that n ! can be very closely approximated by √ 2 πn n n e −n to ap-

proximate i . Then approximate a sum by an integral (see Problem 2.23 ) and consult

tables of values for the error function erf( x )= 0 e −t 2 dt .
9.8 Let 0

y . Show that x + √ y

≥ √ y . ≤ x ≤ − x

CIRCUIT MODELS AND MEASURES

9.9 Provide an algorithm that produces a formula for each circuit of fan-out 1 over a basis
that has fan-in of at most 2.
9.10 Show that any monotone Boolean function f ( n )

n

: B →B

canbeexpandedonits

first variable as

f ( x 1 , x 2 , ... , x n )= f ( 0, x 2 , ... , x n ) ∨ ( x 1 ∧ f ( 1, x 2 , ... , x n ))

9.11 Show that a circuit for a Boolean function (one output vertex) over the standard basis
can be transformed into one that uses negation only on inputs by at most doubling the
number of AND , OR ,and NOT gates and without changing its depth by more than a
constant factor.
Hint: Find the two-input gate closest to the output gate that is connected to a NOT
gate. Change the circuit to move the NOT gate closer to the inputs.

RELATIONSHIPS AMONG COMPLEXITY MEASURES

9.12 Using the construction employed in Theorem 9.2.1 , show that the depth of a function
f :

n m

B →B

in a circuit of fan-out s over a complete basis Ω of fan-in r satisfies the

inequality

D s , Ω ( f ) ≤ D Ω ( f )( 1 + l (Ω) + l (Ω) log s ( rC s , Ω ( f ) /D ))