Information Technology Reference
In-Depth Information
9.13 Show that there are ten functions
f
with
L
Ω
(
f
)=
2 that are dependent on two
variables and that each can be realized from a circuit for
f
(
1
)
mux
plus at most one instance
of
NOT
on an input to
f
(
1
)
mux
and on its output.
9.14 Extend the upper bound on depth versus formula size of Theorem
9.2.2
to monotone
functions.
LOWER-BOUND METHODS FOR GENERAL CIRCUITS
9.15 Show that the function
f
(
x
1
,
x
2
,
...
,
x
n
)=
x
1
∧
x
2
∧···∧
x
n
has circuit size
(
n
−
1
)
/
(
r
−
1
)
log
r
n
over the basis containing the
r
-input
AND
gate.
and depth
9.16 The parity function
f
(
n
)
n
:
B
→B
has value 1 when an odd number of its variables
have value 1 and 0 otherwise. Derive matching upper and lower bounds on the size
and depth of the smallest and shallowest circuit(s) for
f
(
n
)
⊕
over the basis
B
2
.
⊕
9.17 Show that the function
f
(
n
)
mod
4
defined to have value 1 if the sum of the
n
inputs
modulo 4 is 1 can be realized by a circuit over the basis
B
2
whose size is 2
.
5
n
+
O
(
1
)
.
Hint:
Show that the function is symmetric and devise a circuit to compute the sum of
threebitsasthesumoftwobits.
9.18 Over the basis
B
2
derive good upper and lower bounds on the circuit size of the func-
tions
f
(
n
)
4
and
f
(
n
)
5
n
n
:
B
→B
:
B
→B
defined as
f
(
n
)
4
=((
y
+
2
)mod
4
)mod
2
f
(
n
5
=((
y
+
2
)mod
5
)mod
2
Here
y
=
i
=
1
x
i
and
and
+
denote integer addition.
9.19 Show that the set of Boolean functions on two variables that depend on both variables
contains only
AND
-type and parity-type functions. Here an
AND
-type function
com-
putes
(
x
a
y
b
)
c
for Boolean constants
a
,
b
,
c
whereas a
parity-type function
computes
∧
c
for some Boolean constant
c
.
9.20 The threshold function
τ
(
n
)
t
x
⊕
y
⊕
n
on
n
inputs has value is 1 if
t
or more inputs
are 1 and 0 otherwise. Show that over the basis
B
2
that
C
B
2
(
τ
(
n
)
:
B
→B
)
≥
2
n
−
4.
2
9.21 A formula for the parity function
f
(
n
)
n
⊕
,
c
:
B
→B
on
n
inputs is given below. Show
that it has circuit size exactly 3
(
n
−
1
)
over the standard basis when
NOT
gates are not
counted:
f
(
n
)
⊕
,
c
=
x
1
⊕
x
2
⊕···⊕
x
n
⊕
c
9.22 Show that
f
(
n
)
⊕
,
c
has circuit size exactly 4
(
n
−
1
)
over the standard basis when
NOT
gates
are counted.
9.23 Show that
f
(
n
)
,
c
has circuit size exactly 7
(
n
−
1
)
over the basis
{∧
¬}
,
.
⊕
Search WWH ::
Custom Search