Information Technology Reference
In-Depth Information
Since only the
k
th element of
D
i
is needed, it is not necessary to merge all the elements
in each set when two sets are merged. To see which elements need to be merged, let
Δ
i
(
j
)=
U
a
i
,
s
−
1
,
s−
1
Δ
i
(
j
)
is a set of size 2
j
∪
U
a
i
,
s
−
2
,
s−
2
∪···∪
U
a
i
,
j
,
j
.Then
D
i
−
−
1. Observe
that the
k
th element of
D
i
can be obtained by merging elements of rank
k
and
k
−
1of
Δ
i
(
1
)
with the element of
U
a
(
i
,0
)
,0
. (They all have value 0 or 1.) The middle element is the
k
th element in
D
i
. To obtain elements of rank
k
and
k
−
1of
Δ
i
(
1
)
, the elements of rank
k
,
k
3of
Δ
i
(
2
)
aremergedwiththetwoelementsof
U
a
i
,1
,1
and the
middle two taken. In general, to obtain the elements of rank
k
,
...
,
k
−
1,
k
−
2and
k
−
2
j
+
1of
Δ
i
(
j
)
,
−
2
j
+
1
+
1of
Δ
i
(
j
+
1
)
are merged with the 2
j
elements of
the elements of rank
k
,
...
,
k
−
U
a
i
,
j
,
j
and the middle 2
j
taken.
We now count the number of extra
AND
and
OR
gates needed to perform the merges.
There are 2
s−j
sets
Δ
i
(
j
)
.The2
j
elements needed from these sets are obtained by merging
2
j
+
1
elements of
Δ
i
(
j
+
1
)
with the 2
j
elements of
U
a
i
,
j
,
j
. Since these sets can be merged
in a comparator network with
O
(
j
2
j
)
comparators (see Theorem
6.8.2
), it follows that all
the sets
Δ
i
(
j
)
,0
≤
i
≤
n
−
1, can be formed with
O
(
jn
)
gates for 0
≤
j
≤
s
−
1.
1 shows that a total of
O
(
n
log
2
n
)
extra gates suffice.
Since
O
(
n
log
2
n
)
gates are used to sort the sets
Summing over
j
,0
≤
j
≤
(log
2
n
)
−
2
s−j
{
U
i
,
j
|
0
≤
i
≤
−
1, 0
≤
j
≤
s
−
1
}
,
the desired conclusion follows.
We can now show that a large lower bound on the monotone circuit size of a slice function
implies a large lower bound on its non-monotone circuit size. The importance of this statement
is emphasized by the existence of
NP
-complete slice functions. If such a problem can be shown
to have a super-polynomial slice function, then
P
=
NP
.
THEOREM
9.6.9
Let
f
:
B
n
→B
be a slice function. Then
C
Ω
0
(
f
)+
O
(
n
log
2
n
)
Proof
The first inequality holds because the standard basis
Ω
0
contains the monotone basis.
To establish the second inequality, we convert a circuit over
Ω
0
by moving all negations to
the input variables. This can be done by at most doubling the number of gates.
C
Ω
0
(
f
)
≤
C
Ω
mon
(
f
)
≤
·
2
(See
Problems
9.11
and
2.12
.)
We now show that for slice functions the negation of an input variable
x
i
can be replaced
by the pseudo-negation function
τ
(
n
)
k
,
|
x
|
>k
,atleast
i
. To see this, observe that when
¬
1
=
k
of the variables of
τ
(
n
)
k
,
are 1 and
τ
(
n
)
k
,
|
x
|−
¬i
has value 1. On the other hand,
¬i
<k
, then not enough variables can be 1 for
τ
(
n
)
k
,
|
x
|
when
to have value 1. Finally, when
¬i
=
k
,
τ
(
n
)
k
,
|
x
|
=
0if
x
i
=
1 because not enough of the remaining variables are 1, and
¬i
τ
(
n
)
k
,
i
=
1when
x
i
=
0 by a similar reasoning. Now replace
x
i
with
τ
(
n
)
i
.Since
f
is a
¬
k
,
¬
<k
,a
s
is
τ
(
n
)
k
,
k
-slice,
f
=
0when
<k
,replacing
x
i
by its
pseudo-negation means replacing
x
i
by 0, which can only decrease the circuit output since
it is monotone. Thus,
f
is computed correctly in this case. The same is true if
|
x
|
¬i
.If
x
i
=
1when
|
x
|
|
x
|
>k
,
again by monotoni
ci
ty. Since
τ
(
n
)
k
,
=
k
, the circuit correctly computes
f
for all inputs when
x
i
is replaced by the
i
th pseudo-negation.
i
=
x
i
when
|
x
|
¬
AN NP-COMPLETE SLICE FUNCTION
We now exhibit the language
HALF
-
CLIQUE CENTRAL
SLICE
and show it is
NP
-complete. The characteristic functions of this language are slice func-
tions. It follows from Theorem
9.6.9
that if these slice functions have exponential circuit size,
Search WWH ::
Custom Search