Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

Подождите немного. Документ загружается.

16.7 Reduction Notions 271

of communication complexity. The methods applied are more complicated and

can be seen as a generalization of communication complexity (see, for example,

Beame, Saks, Sun, and Vee (2003)). In particular, generalized rectangles play

a central role in these investigations.

16.7 Reduction Notions

So far we have emphasized the development of methods for proving lower

bounds and applied these methods only on a few example functions. With the

help of suitable reduction concepts, we can extend these results to many more

functions. In this section we will introduce these reduction concepts and give

a few examples of how they are used. We will consider families f =(f

)of

functions such that f

: {0, 1}

p(n)

→{0, 1}

q(n)

for two polynomially bounded

functions p and q. Since we again consider polynomial size to be eﬃciently

computable, f

may have p(n) inputs. In most cases, p(n) will grow linearly.

By considering more than one output (q(n) > 1) we can treat functions like

multiplication in their entirety. All of the reductions we are about to introduce

will have the property that f =(f

) is reducible to g =(g

)iff

can be

eﬃciently represented using g

-gates. Depending on the purpose at hand, we

need to decide how to fairly measure the costs of using these g

-gates.

To make the following deﬁnitions more understandable we ﬁrst introduce

the complexity class

(Nick’s class, named after Nick Pippenger). NC

contains all families f =(f

) of Boolean functions that can be computed by

circuits using arbitrary gates with fan-in 2 in logarithmic depth (and therefore

in polynomial size).

Deﬁnition 16.7.1. A family of functions f =(f

) is a projection of g =

) (denoted f ≤

proj

g) if for some polynomially bounded function r the bits

of f

,...,x

p(n)

) are realized at speciﬁed outputs of g

r(n)

,...,y



(r(n))

where for each 1 ≤ i ≤ p



(r(n)), y

∈{0, 1,x

,...,x

p(n)

, x

p(n)

}. If for each

j ∈{1,...,p(n)} there is at most one i with y

∈{x

, x

}, then the projection

is a read-once projection (denoted f ≤

rop

g).

Deﬁnition 16.7.2. A family of functions f =(f

) is AC

-reducible to g =

) (constant depth reducible, denoted f ≤

g) if there are polynomial-size,

constant-depth circuits for f

that are allowed to use AND- and OR-gates

with unbounded fan-in, NOT-gates, and g

-gates. Each g

-gate is considered

to contribute m to the value of the size of such a circuit.

Deﬁnition 16.7.3. A family of functions f =(f

) is NC

-reducible to g =

) (denoted f ≤

g) if there are polynomial-size circuits of logarithmic depth

for f

using gates with fan-in two and g

-gates. Each g

-gate is considered

to contribute log m to the depth and m to the size of such a circuit.

272 16 The Complexity of Boolean Functions

As always, we want our reductions to be transitive, and this can be easily

shown for all four of these reductions. Furthermore, these reductions can be

ordered as follows:

f ≤

rop

g ⇒ f ≤

proj

g ⇒ f ≤

Once again we omit the easy proofs.

How can we make use of these reducibilities? Projections make our life easy.

In circuits or formulas for g

r(n)

, the variables can simply be replaced according

to the speciﬁcations of the projection. The result is a circuit or a formula

for f

. This shows that C(f

) ≤ C(g

r(n)

), L(f

) ≤ L(g

r(n)

), and D(f

) ≤

D(g

r(n)

). A monotone projection is not allowed to use the negated variables

,...,x

p(n)

. If we use only monotone projections, then the inequalities above

hold for monotone circuits and formulas as well.

In a branching program for g

r(n)

we can replace the variables at the internal

vertices according to the speciﬁcations of the projection. An

-vertex becomes

an x

-vertex if we change the labeling on the out-going edges. An internal

vertex with label 0 can be removed; all edges entering such a vertex can be

routed directly to its 0-child. The same is true for the label 1. From oblivious

branching programs we obtain oblivious branching programs, and the number

of levels cannot increase. However, if we start with k-OBDDs or k-IBDDs, we

are only guaranteed to end up with k-OBDDs or k-IBDDs if the projections

are read-once. This is the reason for introducing ≤

rop

-reductions.

In order to describe the application of the other two reducibilities, we

introduce the complexity classes

and NC

. The class AC

contains all

families f =(f

) of Boolean functions that can be computed by polynomial-

size alternating circuits of depth O(log

n). With the interpretation log

(n)=

1 this is a canonical generalization of the class

. The class NC

contains all

families f =(f

) of Boolean functions that can be computed by polynomial-

size circuits of depth O(log

n) using arbitrary gates of fan-in 2. The following

properties can be easily proved:

• g ∈

and f ≤

g ⇒ f ∈ AC

;

• g ∈

and f ≤

g ⇒ f ∈ NC

So these reductions have the desired and expected properties. Now we will

look at some speciﬁc reductions.

In Theorem 13.6.3 we showed that the circuit value problem

CVP is

P-complete. An instance of CVP consists of a circuit C and an input a of

the appropriate length for C. The task is to evaluate C on input a.Since

CVP ∈ P, CVP ∈ P/poly.Iff =(f

) ∈ P/poly – and therefore computable by

polynomial-size circuits C =(C

)–thenf ≤

rop

CVP:Forf

we select the

description of C

, which consists of constants, and consider the evaluation of

the circuit C

on an input a for f

. The result is f

(a), since C

computes

the function f

.Thuswehaveshownthefollowingresult.

Theorem 16.7.4.

CVP is ≤

rop

-complete for P/poly. 

16.7 Reduction Notions 273

We conclude with the consideration of several frequently used functions,

namely the parity function PAR, the inner product function IP, the majority

function MAJ, the multiplication function MUL (here considered to output all

of the bits of the product), the sum of nn-bit numbers MADD (multiple ad-

dition), the squaring function SQU, the computation of the n most signiﬁcant

bits of the reciprocal of an n-bit number INV (inverse), and the computation

of the n most signiﬁcant bits of the quotient of two n-bit numbers DIV.

Theorem 16.7.5.

• PAR ≤

rop

IP ≤

rop

MUL ≤

rop

SQU ≤

rop

INV ≤

rop

DIV,

• MAJ ≤

rop

MUL,

• MADD ≤

rop

MUL,

• SQU ≤

proj

MUL,and

• MUL ≤

MADD.

Proof. PAR ≤

rop

IP follows from the fact that PAR

(x)=IP

(x, 1

), where

denotes the vector consisting of n 1’s.

TheproofsthatIP≤

rop

MUL, MAJ ≤

rop

MUL, and MADD ≤

rop

MUL

are all based on the same basic idea. When we multiply x and y,thesumofall

k−i

has the place value 2

. This sum doesn’t appear in its pure form in the

product, since there may be carries from earlier positions and because carries

from position k are combined with the sums for positions k +1,k +2,....

However, if we separate the important positions in x and y by suﬃciently

many 0’s, then we can avoid these “overlap eﬀects”. We know that the sum

of all x

for 1 ≤ i ≤ n has a bit length of k = log(n +1). Therefore,

MUL

n+(n−1)(k−1)



)withx



=(x

n−1

, 0

k−1

n−2

, 0

k−1

,...,x

, 0

k−1

)

and y



=(y

, 0

k−1

,...,0

k−1

n−1

) takes on the value of IP

(x, y).

0 x

* y

0 y

Fig. 16.7.1. An illustration of the projection IP ≤

proj

MUL.

To prove that MAJ ≤

rop

MUL we increase the number of inputs to MAJ

by adding constant inputs until the number of inputs is the next larger number

of the form 2

− 1. We do this in such a way that the majority value is not

274 16 The Complexity of Boolean Functions

changed, namely by choosing an equal number of 0’s and 1’s if possible, else

one more 1 than 0. Now if we multiply the new input x by y and separate the

numbers with 0’s as in the proof that IP ≤

rop

MUL, and set all the y

to 1,

then the resulting product is the binary representation of the sum of all x

Since we have m =2

− 1 bits, the most signiﬁcant bit of the sum indicates

the majority value. For the proof that MADD ≤

rop

MUL we need to get the

binary representation of the sum of all x

where this time each x

is itself an

n-bit number. This sum has a bit length of at most n + log n, so it suﬃces

to separate things with log n 0’s.

For the proof of MUL ≤

rop

SQU we consider for factors x and y of bit

length n the number z =(x, 0

n+1

,y) and claim that MUL

(x, y) is contained

in SQU

3n+1

(z). This is because

z

=(x·2

2n+1

+ y)

= x

· 2

4n+2

+ x·y·2

2n+2

+ y

Since y

and x·y have a bit length of 2n, there are no overlaps and

SQU

3n+1

(z) contains x·y.

The most diﬃcult portion of this proof is showing that SQU ≤

rop

INV.

The basic idea is to make use of the equality

1+q + q

+ q

+ ··· =1/(1 − q)

for 0 ≤ q<1. Here we see that the square of q is one of the summands of the

reciprocal of 1 − q. Ideally we would like to write 1 − q as a projection of q

and again make sure that no undesired overlaps occur when we sum all the

’s. Unfortunately this doesn’t quite work, since it is not possible to express

1 − q as a projection of q.

We want to square the number x =(x

n−1

,...,x

). So we form the (10n)-

bit number y with y := x·2

−t

−T

, t := 4n,andT := 10n.The

extra summand 2

−T

guarantees that we can write 1 −y as a projection of

x.Furthermore,2

−T

is small enough that it doesn’t produce any undesired

overlaps. Figure 16.7.2 doesn’t use the correct parameters, but is structurally

correct and shows how we get 1 −y.

1=1. 000000000

y =0. 000x

001

1 −y =0. 111x

111

Fig. 16.7.2. The computation of 1 −y.

It remains to show that we can ﬁnd x

in the 10n most signiﬁcant bits

of Q := 1/(1 −y).

16.7 Reduction Notions 275

Q =1+y + y

+ y

+ ···

=1+(x·2

−t

−T

)+(x·2

−t

−T

)

+(x·2

−t

−T

)

+ ···

=1+x·2

−t

+ x

· 2

−2t

+ remainder.

The remainder can be approximated for n ≥ 2by

−10n

−12n

−20n

+2· 2

−9n

< 2

−8n

So the 8n + 1 most signiﬁcant bits of 1/(1 −y) represent the number 1 +

x·2

−4n

+ x

· 2

−8n

.Sincex

≤ 2

, once again we have no overlaps, and

we ﬁnd x

in INV

10n

applied to 1 −y.

Let y be an n-bit string such that y = 1, then INV

(x) = DIV

(y, x)

and so INV ≤

rop

DIV; and SQU

(x)=MUL

(x, x)soSQU≤

proj

MUL. For

the latter projection each x

-bit is read twice.

The ordinary multiplication procedure taught in grade school requires

computing the product x

for all i and j with 0 ≤ i, j ≤ n − 1. For this n

gates and depth 1 suﬃce. The “multiplication matrix” shown in Figure 16.7.1

can be interpreted as the addition of n numbers of bit length 2n−1. If we add

n − 1 additional summands each with the value 0, then we can use a single

MADD

2n−1

-gate to compute MUL

(x, y). 

To estimate the complexity of Boolean functions we begin by devel-

oping methods for proving lower bounds in the various models being

considered. These methods are ﬁrst applied to simple-looking functions

and then extended to many other functions with the help of suitably

deﬁned reducibilities.

Final Comments

For discrete optimization problems the design of an algorithm in most cases is

a trivial task. The search space – the set of possible solutions – is ﬁnite, and it

is possible to go through the elements of the search space, evaluate them, and

then select the optimal solution. But normally the size of the search space

grows exponentially with the length of the problem description, so a brute

force exploration of the search space for all lengths of interest is generally

not practical. Thus the only algorithms that are really of interest are those

that can get by with reasonable amounts of time and storage space. Users

of algorithms might be satisﬁed with randomized algorithms that work with

a small probability of error or failure, or with algorithms that only produce

nearly optimal results. And often they only require algorithms for special cases

of a more general problem.

Complexity theory is the discipline that tries to discover the border be-

tween problems that are eﬃciently solvable and those that are not. Complexity

theory must react to new developments in the design of algorithms and deal

with such things as problems with small numbers, approximation problems,

black box problems (where only incomplete information about the input is

available), and problems with ﬁxed input length (as occur, for example, in

the design of hardware).

There are many important problems for which no eﬃcient algorithm is

known, but for which we also have no proof that an eﬃcient algorithm is

impossible. In this rigorous sense, complexity theory has failed. But it has

been largely successful in making statements regarding the relative diﬃculty

of important problems. Such statements have the following form: “If A is eﬃ-

ciently solvable, then so is B”, or equivalently, “If B is not eﬃciently solvable,

then neither is A”. Furthermore, it has been possible not only to compare

pairs of problems in this way, but also to compare problems to entire classes

of problems and to compare classes of problems with each other. The theory

NP-completeness is a milestone of scientiﬁc achievement, and new devel-

opments such as probabilistically checkable proofs have built an impressive

structure on this foundation. If one is willing to accept well-founded hypothe-

278 Final Comments

ses, then one obtains a fairly comprehensive view of where the borders for the

design of eﬃcient algorithms lie.

Complexity theory has not only reacted to algorithmic questions but has

also had an independent development. The structural results obtained in this

way can often be applied to gain an even clearer view of the complexity of

speciﬁc problems.

If we are only interested in rigorous lower bounds on the resources required

to solve problems – bounds that do not depend on any hypotheses – then the

results are sobering. The situation is somewhat better in the black box scenario

and in situations where we place bounds on some additional resource such as

parallel computation time, or depth, or storage space. Trade-oﬀ results reveal

the potential of the methods currently available for lower bounds on resource

requirements.

In summary, complexity theory can be satisﬁed that it has found at least

partial solutions to all new options for the design of algorithms. Complexity

theory also has a future, since there are central problems that remain unsolved

and since developments in the design of algorithms will continue to raise new

and practically relevant questions.

Appendix

A.1 Orders of Magnitude and O-Notation

As was discussed in Chapter 2, the computation time of algorithms is mea-

sured in terms of parameters such as the length of the input. The most com-

monly used measure of computation time is the worst-case computation time

with respect to the unit cost model. Computation times are then functions

t: N → N that increase monotonically. But computation times can only rarely

be computed exactly, and so they are bounded from above and below. In es-

timates like





≤ n

/2 functions arise that are no longer integer-valued. For

this reason we will work here with functions f : N → R

We want to compare computation times in such a way that “constant

factors don’t matter”. Since its ﬁrst use by Bachmann in 1892, O-notation

(pronounced “big O”) has established itself as the way to measure the growth

rate, or order of magnitude, of functions f : N → R

, and therefore of com-

putation times.

Our goal is to deﬁne the relations “≤”, “≥”, “=”, “<”, and “>” between

functions, but ﬁrst we will replace the strict deﬁnition f ≤ g (namely, f ≤ g

if and only if f(n) ≤ g(n)forall n ∈ N) with a weaker condition:

Deﬁnition A.1.1. f = O(g) has the interpretation that asymptotically f

grows no faster than g, and is deﬁned by the condition that f(n)/g(n) is

bounded above by a constant c.

The notation f = O(g) has the disadvantage of suggesting that O(g)=f,

but this notation is not even deﬁned. It is therefore useful to think of “≤”

when one sees O, so that it becomes clear that these relationships must be

read from left to right and are not reversible. Or one can think of O(g)asthe

set of all functions f such that f = O(g). In this case, f ∈ O(g)wouldbe

more suggestive notation. The notation O(f

)=O(g) is understood to mean

that whenever h = O(f), then h = O(g). So we interpret

+ n

1/2

≤n

+ n = O(n

)=O(n

)

280 A Appendix

as follows: n

+n = O(n

), since (n

+n)/n

≤ 2. Furthermore, every function

h with h(n)/n

≤ c also has the property that h(n)/n

≤ c. With such a chain

of “equations”, we may omit the middle part and conclude that n

+ n =

O(n

). Now it is clear why the use of the equality symbol in O-notation has

proved to be so advantageous. Otherwise, the previous relationship would have

to be written as

+ n

1/2

≤n

+ n ∈ O(n

) ⊆ O(n

) ,

and the mixture of “≤”, “∈”, and “⊆” in one formula is confusing.

The following computation rules for O are useful:

• c · f = O(f)forc ≥ 0,

• c · O(f )=O(f)forc ≥ 0,

• O(f

)+··· + O(f

)=O(f

+ ··· + f

)=O(max{f

,...,f

}) for any

constant k,and

• O(f) · O(g)=O(f · g).

The ﬁrst two relationships are obvious; the third follows from

· f

(n)+···+ c

· f

(n) ≤ (c

+ ···+ c

) · (f

(n)+···+ f

(n))

≤ k · (c

+ ···+ c

) · max{f

(n),...,f

(n)} ,

and the fourth from

· f (n)) · (c

· g(n)) = (c

· c

) · f (n) · g(n) .

Once we have expressed “asymptotically ≤”asO, the deﬁnitions of

“asymptotically ≥”, and “asymptotically =”, follow in the obvious way:

• f = Ω(g) (read “f is big omega of g”) has the interpretation that f grows

asymptotically at least as fast as g, and is deﬁned by g = O(f).

• f =Θ(g) (read “f is big theta of g”) has the interpretation that asymp-

totically f and g grow at the same rate and is deﬁned by f = O(g)and

g = O(f).

Finally, we come to the deﬁnitions of “asymptotically <” and “asymptot-

ically >”:

• f = o(g) (read “f is little o of g”) has the interpretation that asymptoti-

cally f grows more slowly than g and is deﬁned by the condition that the

sequence f(n)/g(n) approaches 0.

• f

= ω(g) (read “f is little omega of g”) has the interpretation that asymp-

totically f grows more quickly than g andisdeﬁnedbyg = o(f).

If we were to use the strict deﬁnition of f ≤ g, namely that f(n) ≤ g(n)

for all n, then many pairs of functions that are asymptotically comparable

(like n

and n + 10, for example), would not be comparable. In this case,

A.1 Orders of Magnitude and O-Notation 281

n+10 = O(n

); in fact, n+10 = o(n

). Nevertheless, not all pairs of monotone

functions are asymptotically comparable. Let

f(n):=

⎧

⎨

⎩

n! n even

(n−1)! n odd

and

g(n):=

⎧

⎨

⎩

(n−1)! n even

n! n odd.

Then f and g are monotone increasing, but f(n)/g(n)=n for even n,and

g(n)/f(n)=n for odd n, so neither is bounded above by a constant. Thus

neither f = O(g)norg = O(f) are true. The runtimes of most algorithms,

however, are asymptotically comparable.

Finally, we want to order the growth rates that typically occur as com-

putation times. The growth rates log log n, log n, n, 2

,and2

serve as

a basis. The diﬀerence between each successive pair is exponential since

log log n

=logn and 2

log n

= n.Wewilluselog

n as an abbreviation for

(log n)

. Then for all constants k>0andε>0,

(log log n)

= o(log

n),

log

n = o(n

= o(2

) .

As an example, we will show the second relation. We must show that

lim

n→∞

(log

= 0. It is a simple fact of analysis that for α>0, lim

n→∞

0 if and only if lim

n→∞

=0.Letα := 1/k and δ := ε/k. Then we need to

check if lim

n→∞

(log n)/n

= 0. The functions log n and n

can be extended

in a canonical way to log x and x

, functions on R

. By l’Hospital’s rule

lim

x→∞

log x

= lim

x→∞

log x

(A.1)

= lim

x→∞

−δ

δ ln 2

(A.2)

and this limit is clearly 0. The other relationships follow in a similar fashion.

From these follow many more relationships, e.g., n log n = o(n

), since log n =

o(n). As an example, we obtain the following sequence of asymptotically ever

faster growing orders of magnitude, where 0 <ε<1: