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