Information Technology Reference
In-Depth Information
D
(
k
)=
D
(
k
−
1
)+
4, where
D
(
1
)=
0. The solution to this recurrence is
D
(
k
)=
4
(
k
−
1
)
.
If
n
is not of the form 2
k
−
1, we increase
n
to the next largest integer of this form, which
implies that
k
=
log
2
(
n
+
1
)
. Using the upper bounds on the size of circuits to compute
τ
(
n
)
t
,
¬i
(
x
)
for 1
≤
t
,
i
≤
n
, we have the desired conclusion.
9.6 Lower-Bound Methods for Monotone Circuits
The best lower bounds that have been derived on the circuit size over complete bases of Boolean
functions on
n
variables are linear in
n
. Similarly, the best lower bounds on formula size that
have been derived over complete bases are at best quadratic in
n
. As a consequence, the search
for better lower bounds has led to the study of monotone circuits (their basis is
Ω
mon
)for
monotone functions. In one sense, this effort has been surprisingly successful. Techniques
have been developed to show that some monotone functions have exponential circuit size.
Since most monotone Boolean functions on
n
variables have circuit size
Θ(
2
n
/n
3
/
2
)
,thisis
a strong result. On the other hand, the hope that such techniques would lead to strong lower
bounds on circuit size for monotone functions over complete bases has not yet been realized.
Some monotone functions are very important. Among these are the
clique function
f
(
n
)
f
(
n
)
clique
,
k
n
(
n−
1
)
/
2
clique
,
k
:
B
→B
.
is associated with a family of undirected graphs
G
=(
V
,
E
)
on
n
=
|
V
|
|
E
|≤
n
(
n
−
1
)
/
2 edges, where
V
=
{
1, 2, 3,
...
,
n
}
vertices and
.
The variables of
f
(
n
)
,where
x
i
,
j
=
1ifthereisan
edge between vertices
i
and
j
and
x
i
,
j
=
0 otherwise. The value of
f
(
n
)
clique
,
k
are denoted
{
x
i
,
j
|
1
≤
i<j
≤
n
}
clique
,
k
on these variables
is 1 if
G
contains a
k
-clique
,asetof
k
vertices such that there is an edge between every pair of
vertices in the set. The value of
f
(
n
)
clique
,
k
is 0 otherwise. Clearly
f
(
n
)
clique
,
k
is monotone because
increasing the value of a variable from 0 to 1 cannot decrease the value of the function.
As stated in Problem
8.24
,the
CLIQUE
problem is
NP
-complete. Since an instance of
CLIQUE
on a graph with
n
vertices can be converted to the input format for
f
(
n
)
clique
,
k
in time
polynomial in
n
,ifthecircuitsizefor
f
(
n
)
clique
,
k
over a complete basis can be shown to be
superpolynomial, then from Corollary
3.9.1
,
P
=
NP
.
There are important similarities and differences between monotone and non-monotone
functions. Every non-monotone function can be realized by a circuit over the standard basis
Ω
0
in which negations are used only on inputs. (See Problem
9.11
.) On the other hand, since
circuits without negation compute only monotone functions (Problem
2
), negations on inputs
are essential.
The first results showing the existence of monotone functions such that their monotone
and non-monotone circuit sizes are different were obtained for multiple-output functions. We
illustrate this approach below for the
n
-input binary sorting function,
f
(
n
)
sort
, whose monotone
circuit size is shown to be
Θ(
n
log
n
)
. As stated in Problem
2.17
, this function can be realized
by a circuit whose size over
Ω
0
is linear in
n
.
We introduce the path method to show that a gap exists between the monotone and non-
monotone circuit size of a family of functions. In Section
9.6.3
the approximation method
is introduced and used to show that the clique function
f
(
n
)
clique
,
k
has exponential monotone
circuit size.
Search WWH ::
Custom Search