Information Technology Reference
In-Depth Information
B i , v for different values of v are disjoint, f ( c )
i , v ( b ) can be realized as the OR of at most 2 n−k
two-input OR 's . Thus , a l l f ( c )
minterms using at most 2 n−k
i , v ( b ) ,1
i
p , can be realized
with p 2 n−k + 2 n−k +( n
2 ) 2 ( n−k ) / 2 gates.
Consulting ( 2.19 ), we see that to realize f we must add one AND gate for each i and tuple
v . We must also add the number of two-input OR gates needed to combine these products.
Sincethereareatmost p 2 s products, at least p 2 s OR gates are needed for a total of p 2 s + 1
gates.
Let C k , s ( f ) be the total number of gates needed to realize f in the ( k , s ) -Lupanov repre-
sentation. C k , s ( f ) satisfies the following inequality:
k
O ( 2 k + s )+ O ( 2 ( n−k ) )+ p ( 2 n−k + 2 s + 1 )
C k , s ( f )
2 k /s
2 k /s + 1, this expands to
Since p =
, p
O ( 2 k + s )+ O ( 2 n−k )+ 2 n
s
+ 2 k + s + 1
s
C k , s ( f )
log 2 n 2 + 2and
Now let k =
3 log 2 n
and s =
n
5 log 2 n
.Then, k + s
n
log 2 n 3 . As a consequence, for large n ,wehave
n
k
n
O 2 n
n 2 + O 2 n
n 3 +
2 n
C k , s ( f )
( n
5 log 2 n )
We summarize the result in a theorem.
THEOREM 2.13.2 For each > 0 there exists some N 0 > 1 such that for all n ≥ N 0 every
Boolean function f :
n
B
→B
has a circuit size complexity satisfying the following upper bound:
2 n
n ( 1 + )
Since we show in Section 2.12 that for 0 << 1 almost all Boolean functions f :
C Ω 0 ( f )
n
B
B
have a circuit size complexity satisfying
2 n
n ( 1
2 n 2
C Ω 0 ( f )
)
for n
/ 2 )] , this is a good lower bound.
.......................................
Problems
MATHEMATICAL PRELIMINARIES
) / ]log 2 [( 3 e ) 2 ( 1
2 [( 1
2.1 Show that the following identities on geometric series hold:
s
a j = ( a s + 1
1 )
( a
1 )
j = 0
s
a
a j j =
1 ) 2 ( sa s + 1
( s + 1 ) a s + 1 )
( a
j = 0
 
Search WWH ::




Custom Search