Logic Circuits - Models of Computation: Exploring the Power of Computing - page 46

A natural question to ask is whether there is a function that has large size in all five normal
forms. The answer is yes. This is true of the Boolean function on n variables whose value is 1
when the sum of its variables is 0 modulo 3 and is 0 otherwise. It has exponential-size DNF,
CNF, and RSE normal forms. (See Problem 2.10 .) However, its smallest circuit is linear in n .
(See Section 2.11 .)

2.4 Reductions Between Functions
A common way to solve a new problem is to apply an existing solution to it. For example, an
integer multiplication algorithm can be used to square an integer by supplying two copies of
the integer to the multiplier. This idea is called a “reduction” in complexity theory because we
reduce one problem to a previously solved problem, here squaring to integer multiplication. In
this section we briefly discuss several simple forms of reduction, including subfunctions. Note
that the definitions given below are not limited to binary functions.

DEFINITION 2.4.1 Afunction f : A

n m r s

→A is a reduction to the function g : A →A

through application of the functions p :

A

s

→A

m and q :

A

n

→A

r

for all x

∈A

n :

if

f ( x )= p ( g ( q ( x )))

As suggested in Fig. 2.4 , it follows that circuits for q , g and p can be cascaded (the output
of one is the input to the next) to form a circuit for f . Thus, the circuit size and depth of f ,
C ( f ) and D ( f ) , satisfy the following inequalities:

C ( f ) ≤ C ( p )+ C ( g )+ C ( q )

D ( f ) ≤ D ( p )+ D ( g )+ D ( q )

A special case of a reduction is the subfunction, as defined below.

DEFINITION 2.4.2 Let g : A

m .A subfunction f of g is a function obtained by assigning
values to some of the input variables of g , assigning (not necessarily unique) variable names to the
rest, deleting and/or permuting some of its output variables. We say that f is a reduction to g via
the subfunction relationship .

n

→A

f

x

f ( x )= p ( g ( q ( x )))

q g p

Figure 2.4 The function f is reduced to the function g by applying functions p and q to prepare
the input to g and manipulate its output.