Information Technology Reference
In-Depth Information
are absent. The unassigned variables are between vertices in
S
, between vertices in
R
and
S
,
and between vertices in
V
and
S
,ofwhichthereare8
n
2
−
3
n
. Fix these unassigned edges
so that the number of edges between vertices in
V
∪
R
∪
S
is
e
(
5
n/
2
)
/
2
−
k
,1
≤
k
≤
n
.
There are sufficiently many unassigned edges to do this.
We now show that
G
contains an
n/
2-clique or has more than
k
edges if and only if
G
contains an 5
n/
2-clique or has more than
edges. If
G
has a
n/
2-clique,
the edges between
V
and
R
combined with the edges between vertices in
R
and those in
G
constitute a 5
n/
2cliquesince5
n/
2verticesin
V
e
(
5
n/
2
)
/
2
∪
R
are completely connected. If
V
has more than
k
edges, since there are exactly
e
(
5
n/
2
)
/
2
−
k
edges between vertices in
edges. On the other hand, if
G
has a
(
5
n/
2
)
-clique,
because there is at least one absent edge between each pair of vertices
(
r
i
,
s
i
)
,1
S
,
G
has at least
V
∪
R
∪
e
(
5
n/
2
)
/
2
≤
i
≤
2
n
,
the largest clique on vertices in
R
S
has size 2
n
. Thus,theremustbea
(
n/
2
)
-clique
on vertices in
V
;thatis,
G
contains a
(
n/
2
)
-clique. Similarly, since the number of edges
between vertices in
V
and those in
R
∪
k
,if
G
contains at least
∪
S
is exactly
e
(
5
n/
2
)
/
2
−
edges,
G
must contain at least
k
edges.
The membership of graph
G
in
HALF
-
CLIQUE
is determined by specializing the graph
G
by mapping its edge variables to the constants 0 and 1 or to variables of
G
.Thu ,
the function testing
G
's membership is obtained through a subfunction reduction of the
function testing
G
's membership. (See Definition
2.4.2
.) Thus, at no increase in circuit
size, for any
k
a circuit for
f
(
n
)
clique
,
e
(
5
n/
2
)
/
2
[
k
]
can be obtained from a circuit for
f
(
n
)
clique slice
.
Thus, the circuit size for the latter is at least as large for the former, which gives the second
result of the theorem.
n/
2
The statement that for
k<e
(
n/
2
)
,
f
(
n
)
clique
,
[
k
]
=
τ
e
(
n
)
k
+
1
follows from the ob-
servation that for these values of
k
the value of the clique function on inputs of weight
e
(
n/
2
)
n/
2
−
1orlessis0.
=
NP
can be limited to the study
of the monotone circuit size of the central slice of certain monotone functions. Other central
slices of
NP
-complete problems have been shown to be
NP
-complete also. (See the Chapter
Notes.)
As this theorem indicates, the search for a proof that
P
9.7 Circuit Depth
Circuit depth and formula size are exponentially related, as shown in Section
9.2.3
.Inthis
section we examine the depth of circuits whose operations have either bounded or unbounded
fan-in. As seen in Chapter
3
, circuits of bounded fan-in are useful in classifying problems by
their complexity and in developing relationships between time and space and circuit size and
depth.
Circuits of unbounded fan-in are constructed of
AND
and
OR
gates with potentially un-
bounded fan-in whose inputs are the outputs of other such gates or literals, namely, variables
and their negations. Every Boolean function can be realized by a circuit of unbounded fan-in
and bounded depth, as is seen by considering the DNF of a Boolean function: it corresponds to
a depth-2, unbounded fan-in circuit. Knowledge of the complexity of bounded-depth circuits
may shed light on the complexity of bounded-fan-in circuits.
Search WWH ::
Custom Search