Information Technology Reference
In-Depth Information
n/
(
k
−
correspond to each graph. To see this, observe that there are
1
)
!
ways to permute
the elements in each of the first
w
sets and
n/
(
k
−
1
)
!
ways to permute the elements in
each of the remaining
k
−
−
w
sets. Also, each of the first
w
(the last
k
−
−
w
)setshave
1
1
thesamesizeandcanbeorderedinanyof
w
!
(
(
k
−
−
w
)!
) ways without changing the
1
graph.
APPROXIMATOR CIRCUITS
It simplifies the development of lower bounds to assume that each
AND
gate in a circuit is followed by an
OR
gate and vice versa and that the output gate is an
AND
gate. This requirement can be met by interposing between successive
AND
(
OR
)gates
an
OR
(
AND
) gate both of whose inputs are connected together. Since this transformation at
most triples the number of gates, an exponential lower bound on the size of the transformed
circuit yields an exponential lower bound on the size of the original circuit.
A monotone circuit for
f
(
n
)
{
x
i
,
j
|
≤
i<
clique
,
k
has(edge)variablesdrawnfromtheset
1
j
. The approximation to an input variable
x
i
,
j
is
x
i
,
j
itself. Gates in a circuit are succes-
sively replaced by approximator circuits starting with a gate that is at greatest distance from the
root (output vertex) and continuing with previously unvisited gates at greatest distance from
the root. Thus, when an
AND
or
OR
gate is replaced, its inputs have previously been replaced
by functions
f
l
and
f
r
that approximate the functions
g
l
and
g
r
computed in the original
circuit.
Approximations to
AND
(
≤
n
}
∧
∨
, respectively. As seen
below, the approximation given to a gate is context dependent. Approximations are defined
in terms of endpoint sets. Given a set of edge variables, for example
∧
)and
OR
(
∨
) gates are denoted
and
,its
associated
endpoint set
is the set of vertex indices used to define the edge variables, which is
{
{
x
1,2
,
x
1,3
,
x
2,3
,
x
1,4
}
in this example. Given a term
t
(a product (
AND
)orsum(
OR
) of edge variables),
the endpoint set associated with it,
E
(
t
)
, is the endpoint set of the edge variables appearing in
the term. For example, if
t
=
x
1,2
1, 2, 3, 4
}
∧
x
1,3
∧
x
2,3
∧
x
1,4
or
t
=
x
1,2
∨
x
1,3
∨
x
2,3
∨
x
1,4
,then
E
(
t
)=
{
1, 2, 3, 4
}
.The
endpoint size
of a term
t
, denoted
|
E
(
t
)
|
, is the number of indices
in
E
(
t
)
.
Consideragatetobeapproximated.Letitstwoinputsbefromgatesthatcomputefunc-
tions
f
l
and
f
r
. Like any function,
f
r
and
f
l
can be represented in either the monotone SOPE
or POSE form. (All SOPEs and POSEs in this section are monotone.) The approximation
rules for
AND
and
OR
gates are described below and denoted
∧
and
∨
, respectively. Here we
(
k
let
p
=
−
1
)
/
2
and
q
=
n/
(
4
k
)
.
∧
: The approximation
f
l
∧
f
r
in the sum-of-
products expansion (SOPE) and eliminating all product terms whose endpoint set contains
more than
p
vertices. It follows that
f
l
∧
f
r
to
f
l
∧
f
r
is obtained by representing
f
l
∧
f
l
∧
f
r
≥
f
r
.
∨
: The approximation
f
l
∨
f
r
in the product-of-
sums expansion (POSE) and eliminating all sum terms whose endpoint set contains more
than
q
vertices. It follows that
f
l
∨
f
r
to
f
l
∨
f
r
is obtained by representing
f
l
∨
f
l
∨
f
r
≤
f
r
.
f
l
∧
f
l
∨
f
r
, if a positive test input
x
causes the output
of the approximated circuit to have value 0 when it should have value 1, then there is an
approximated
AND
gate (including the output gate) that has value 0 on
x
when it should have
value 1. Similarly, if there is a negative test input
x
that causes the approximated output to be
1 when it should be 0, there is an approximated
OR
gate that has value 1 on
x
when it should
have value 0. We now examine the performance of approximator circuits.
Since
f
l
∧
f
r
≥
f
r
and
f
l
∨
f
r
≤
Search WWH ::
Custom Search