Information Technology Reference
In-Depth Information
LOWER BOUNDS TO FORMULA SIZE
9.24 Show that the multiplexer function f ( p )
mux can be realized by a formula of size 32 p
2
in which the total number of address variables is 2 ( 2 p
1 ) .
Hint: Expand the function f ( p )
mux as suggested below, where a ( k ) denotes the k com-
ponents of a with smallest index and P = 2 p :
f ( p )
mux ( a ( p ) , y P− 1 , ... , y 0 )= f ( 1 )
mux ( a p− 1 , f ( p− 1 )
mux ( a ( p− 1 ) , y P− 1 , ... , y P/ 2 ) ,
f ( p− 1 )
mux ( a ( p− 1 ) , y P/ 2 1 , ... , y 0 ))
Also, represent f ( 1 )
mux as shown below.
f ( 1 )
mux ( a , y 1 , y 0 )=( a
y 0 )
( a
y 1 )
9.25 Show that Neciporuk's method cannot provide a lower bound larger than O ( n 2 / log n )
for a function on n variables.
9.26 Derive a quadratic upper bound on the formula size of the parity function f ( n )
over
the standard basis.
9.27 Neciporuk's function is defined in terms of an
n/m
×
m matrix of Boolean variables,
X =
{
x i , j }
, m =
log 2 n
+ 2, and a matrix
Σ
=
{
σ i , j }
ofthesamedimen-
sions in which each entry σ i , j is a distinct m -tuple over
B
containing at least two 1s.
Neciporuk's function, N ( X ) ,isdefinedas
N ( X )=
i , j
x i , j
k =
x k , l
1
( k = i )
l such that
σ i , j ( l )= 1
Here denotes the exclusive or operation. Show that this function has formula size
Ω( n 2 / log n ) over the basis B 2 .
9.28 Use Krapchenko's method to derive a lower bound of n 2 on the formula size of the
parity function f ( n )
n
.
9.29 Use Krapchenko's method to derive a lower bound of Ω( t ( n
:
B
→B
t + 1 )) on the formula
size over the standard basis of the threshold function τ ( n )
t
t
n
,1
1.
9.30 Generalize Krapchenko's lower-bound method as follows. Let f :
B
n
→B
and let
f 1 ( 0 ) and B
f 1 ( 1 ) .Let Q =[ q i , j ] be defined by q i , j = 1if x i
A
A and
B are neighbors and q i , j = 0 otherwise. Let P = QQ T and P = Q T Q .Then
p r , s is the number of common neighbors to x r and x s in B . The matrices P and
P are symmetri c a nd their largest eigenvalues, λ ( P ) and λ ( P ) , are both non-negative
and λ ( P )= λ ( P ) . Show that
x j
L Ω ( f )
λ ( P )
9.31 Under the conditions of Problem 9.30 ,let
K ( f )= |N
( A , B )
|
2
1
1
D ( f )=
p r , s ,
D ( f )=
p r , s ,
|
B
|
|
B
|
|
A
||
B
|
r , s
r , s
 
Search WWH ::




Custom Search