Information Technology Reference
In-Depth Information
k
The desired conclusion follows from this and the obser vation that p + 1
1 / 2and
n/ ( 2 k ) . That the maximum value of min( k
q + 1
1 / 2, n/ ( 2 k )) is Ω( n 1 / 3 ) under
variation of k is left as a problem. (See Problem 9.38 .)
9.6.4 Slice Functions
Although, as shown above, some monotone functions have exponential circuit size over the
monotone basis, it is doubtful that the methods of analysis used to obtain this result can be
extended to derive such bounds over the standard basis. (See the Chapter Notes.)
This section introduces a note of optimism by showing that the monotone circuit size of
monotone slice functions can provide a strong lower bound on the circuit size of such functions
over the standard basis. In addition, there are NP -complete languages whose characteristic
functions are slice functions. Thus, if such functions can be shown to have super-polynomial
monotone circuit size, P
= NP .
|
x
|
denote the number of 1's in x .Wenowdefinetheslicefunctions.
Let
DEFINITION 9.6.6 Afunction s : B
n
→B
is a slice function if there is an integer 0
k
n
such that s ( x )= 0 if
|
x
|
<k and s ( x )= 1 if
|
x
|
>k .The k th slice of a function
: B n →B
n ,isthefunction f [ k ] :
n
f
, 0
k
B
→B
defined below.
0
|
x
|
<k
f [ k ] ( x )=
f ( x )
|
x
|
= k
1
|
x
|
>k
It should be clear from this definition that slice functions are monotone. Below we show
that if a Boolean function f on n variables has a large circuit size, then one of its slices has a
circuitsizethatdiffersfromthesizeof f by at most a multiplicative factor that is linear in n .
Thus, a function f has a large circuit size if and only if one of its slice functions has a large
circuit size.
We set the stage with a lemma that shows that the circuit size of a Boolean function is
bounded above by the circuit size of its slices plus an additive term linear in its number of
variables.
LEMMA 9.6.9 Let Ω 0 be the standard basis and f : B
n
→B
. Then the following holds, where
C Ω 0 ( f [ 0 ] , f [ 1 ] , ... , f [ n ] ) is the circuit size of all the slices simultaneously:
C Ω 0 ( f )= C Ω 0 ( f [ 0 ] , f [ 1 ] , ... , f [ n ] )+ O ( n )
Proof The goal is to construct a circuit for f given the input tuple x and a circuit for
all the functions f [ 0 ] , f [ 1 ] , ... , f [ n ] . This is easily done. We construct a circuit to count
the number of 1's among the n inputs and represent the result in binary. We then supply
this number as an address to a direct storage address function (multiplexer) where the other
inputs are the values of the slice functions. If the address is
, the output of the multiplexer
is f [ | a | ] . Since, as shown in Lemma 2.11.1 , the counting circuit can be realized with a circuit
of size linear in n , and, as shown in Lemma 2.5.5 , the multiplexer in question can be realized
with a linear-size circuit, the result follows.
|
a
|
We now establish the connection between the circuit size of a function and that of one of
its slices.
 
Search WWH ::




Custom Search