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