Information Technology Reference
In-Depth Information
Proof
The proof follows directly from the dual-rail expansion of Problem
2.12
and the
following lemma.
W
e now
sh
ow that the function
f
(
n
)
NEG
n
defined by
f
(
n
)
n
NEG
(
x
1
,
x
2
,
...
,
x
n
)=
(
x
1
,
x
2
,
...
,
x
n
)
can be realized by circuit size of
O
(
n
2
log
n
)
over
Ω
0
using
:
B
→B
log
2
(
n
+
1
)
negations.
LEMMA
9.5.1
f
(
n
)
n
n
can be realized with
NEG
:
B
→B
log
2
(
n
+
1
)
negations by a circuit over
the standard basis that has size
O
(
n
2
log
n
)
and depth
O
(log
n
)
.
Proof
The
punctured threshold function
τ
(
n
)
t
,
n
¬i
:
B
→B
≤
t
,
i
≤
n
, is defined below.
,1
¬i
(
x
)=
1
j
=
1,
j
=
i
x
j
≥
t
τ
(
n
)
t
,
0ot er ise
This function has value 1 if
t
or more of the variables other than
x
i
have value 1. The
standard threshold function
τ
(
n
)
n
:
B
→B
has value 1 when
t
or more of the variables
t
have value 1. Since the function
(
τ
(
n
)
0,
i
,
τ
(
n
)
i
,
...
,
τ
(
n
)
i
)
is the result of sorting all but
the
i
th input, we know from Theorem
6.8.3
that Batcher's bitonic sorting algorithm will
produce this output with a circuit of size
O
(
n
log
2
n
)
and depth
O
(log
2
n
)
because max
and min of a comparator unit compute
AND
and
OR
on binary inputs. Ajtai, Komlos, and
Szemeredi [
14
] have improved this bound to
O
(
n
log
n
)
but with a very large coefficient,
and simultaneously achieve depth
O
(log
n
)
. Thus, all the functions
¬
¬
n
−
¬
1,
1,
τ
(
n
)
t
,
{
|
1
≤
t
,
i
≤
n
}
¬
i
can be realized with
O
(
n
2
log
n
)
gates and depth
O
(log
n
)
over
Ω
0
.
Observe that for input
x
there is some largest
t
,
t
=
t
0
,suchthat
τ
(
n
)
t
0
(
x
)=
1. If
τ
(
n
)
t
0
,
b
have value 1 when
a
=
0orwhen
a
=
1and
b
=
1 and value
0
otherwise. Then we
can express the implication function by the formula
(
a
i
(
x
)=
1, then
x
i
=
0; otherwise,
x
i
=
1. Let the
implication function
a
⇒
¬
⇒
b
)=
a
∨
b
. It follows that
x
i
=(
τ
(
n
)
τ
(
n
)
t
0
(
x
)
⇒
t
0
,
¬i
(
x
))
because the implication function has value 1 exactly when
x
i
=
0.
We use an indirect method to compute
t
0
.Since
τ
(
n
)
(
x
)=
0for
t>t
0
,
(
τ
(
n
)
(
x
)
⇒
t
t
τ
(
n
)
t
,
¬i
(
x
)) =
1
for
t>t
0
. Also,
b
oth
τ
(
n
)
(
x
)
and
τ
(
n
)
t
,
¬i
(
x
)
have value 1 for
t<t
0
.Using
t
(
x
⇒
y
)=
x
∨
y
,wecanwrite
x
i
as follows:
x
i
=
τ
(
n
)
0
¬i
(
x
)
τ
(
n
)
1
¬i
(
x
)
τ
(
n
)
n
¬i
(
x
)
τ
(
n
)
0,
τ
(
n
)
1,
τ
(
n
)
n−
(
x
)
∨
∧
(
x
)
∨
∧···∧
1
(
x
)
∨
−
1,
τ
(
n
)
t
{
(
x
)
|
≤
t
≤
n
}
The circuit design is complete once a circuit for
1
has been
τ
(
n
)
t
}
from
x
, which, as stated above, can be computed with
O
(
n
log
2
n
)
gates over the standard
basis. Let
s
t
=
τ
(
n
)
{
(
x
)
|
≤
t
≤
n
designed. We begin by using a binary sorting circuit that computes
1
(
x
)
for 1
≤
t
≤
n
.
t
For
n
=
K
−
1,
K
=
2
k
and
k
an integer, we complete the design by constructing
a circuit for the function
ν
(
k
)
:
n
n
, which, given as i
np
ut the decreasing sequence
B
→B
s
1
,
s
2
,
...
,
s
n
(
s
i
≥
s
i
+
1
), computes as its
j
th output
z
j
=
s
j
,1
≤
j
≤
n
.
(The e
1 is considered below.) That is,
ν
(
k
)
(
s
)=
z
,where
z
t
=
τ
(
n
t
(
x
)
.Wegive
a recursive construction of a circuit for
ν
(
k
)
whose correctness is established by induction.
=
2
k
n
−
Search WWH ::
Custom Search