Information Technology Reference
In-Depth Information
To complete the proof we must show that each endpoint is assigned at most
n/
2 values
from
(
n
)
. Consider the sum terms
c
1
,
...
,
c
l
in the POSE of
f
correct
in sequence and
consider a partial mapping from
V
to
(
n
)
that causes at least one variable in each of the
sums
c
1
,
...
,
c
i−
1
to be 1, thereby insuring that the value of each sum is 1. Now consider
the
i
th sum,
c
i
. If the partial mapping assigns value 1 to at least one variable, we move on
to
c
i
+
1
. (It cannot set all variables in
c
i
to 0 because we are considering mappings causing
all terms to be 1.)
We now extend the mapping by considering the set
C
i
of variables of
c
i
that have not
been assigned a value. A given variable
x
a
,
b
in
C
i
has either one or no endpoints (vertices)
previously mapped to an integer in
(
n
)
. If one endpoint, say
a
, has been assigned an
integer, the other endpoint,
b
, can be assigned to at most one of
k
−
2 integers that cause
x
a
,
b
=
1 because endpoint
a
was previously assigned a value in the range
}
together with at least one other vertex and
b
must be different from them. Because there are
most
q
=
{
1, 2,
...
,
k
n/
(
4
k
)
variables of the first type, there are at most
q
(
k
−
2
)
ways to assign the
one endpoint of a variable
x
a
,
b
ofthefirsttypesothat
x
a
,
b
=
1.
Consider now variables of the second type. There are at most
q
(
q
−
1
)
/
2 such variables
and at most
(
q
(
q
1
)
ways to make assignments to both endpoints so that
a variable has value 1. This follows because each endpoint is assigned to a distinct integer
among the first
k
integers in
(
n
)
. Since each endpoint c
an be assigned in the same number
−
1
)
/
2
)
k
(
k
−
of ways, this number is at most
(
q
(
q
1
)
.
It follows that the number of ways to assign
an endpoint so that the
correct and approx-
imate functions differ is at most
q
(
k
−
1
)
/
2
)
k
(
k
−
2
)+
(
q
(
q
−
−
1
)
/
2
)
k
(
k
−
1
)
≤
2
qk
,whichisno
more than
n/
2since
q
=
n/
(
4
k
)
. This is the desired conclusion.
The desired result follows from the above lemmas.
THEOREM
9.6.6
For
n ≥
13
and
8
≤ k ≤ n/
2
, every monotone circuit for the clique function
f
(
n
)
n
(
n
−
1
)
/
2
clique
,
k
:
B
→B
has a circuit size satisfying the following lower bound:
f
(
n
)
clique
,
k
2
(
1
.
8
)
min(
√
k−
1
/
2,
n/
(
2
k
))
1
C
Ω
mon
≥
Thelargestvalueforthislowerboundis
C
Ω
mon
(
f
(
n
)
clique
,
k
)=
2
Ω(
n
1
/
3
)
.
Proof
From the discussion at the beginning of this section, we see that the monotone circuit
size of
f
(
n
)
clique
,
k
is at least
min (
τ
+
/e
AND
,
τ
−
/
(
2
e
OR
))
.Thus,
min
n
!
2
(
n/
2
)
p
+
1
(
n
n
!
(
n/
2
)
q
+
1
(
n
C
Ω
mon
(
f
(
n
)
clique
,
k
)
≥
1
)!
,
−
p
−
−
q
−
1
)!
min
(
n
(
n/
2
)
q
+
1
p
)
p
+
1
q
)
q
+
1
2
(
n/
2
)
p
+
1
,
(
n
−
−
≥
(
k
≤
√
n/
(
2
√
2
)
and
q
=
Let 8
≤
k
≤
n/
2. It follows that
p
=
−
1
)
/
2
n/
(
2
k
)
≤
n/
16. Thus,
p
,
q
≤
n/
10 if
n
≥
13. Hence both
(
n
−
p
)
and
(
n
−
q
)
are at least 9
n/
10, and
min
1
2
(
1
.
8
)
p
+
1
,
(
1
.
8
)
q
+
1
f
(
n
)
clique
,
k
C
Ω
mon
≥
Search WWH ::
Custom Search