Complexity Classes - Models of Computation: Exploring the Power of Computing - page 353

Monotone circuits are constructed of AND and OR gates. The functions computed by
monotone circuits form an asymptotically small subset of the set of Boolean functions. Also,
many important Boolean functions are not monotone, such as binary addition. But even
though monotone circuits are a very restricted class of circuits, the monotone version of CIR -
CUIT VALUE , defined below, is also P -complete.

MONOTONE CIRCUIT VALUE
Instance: A description for a monotone circuit with fixed values for its input variables and
a designated output gate.
Answer: “Yes” if the output of the circuit has value 1.

CIRCUIT VALUE is a starting point to show that many other problems are P -complete. We
begin by reducing it to MONOTONE CIRCUIT VALUE .

THEOREM 8.9.1 MONOTONE CIRCUIT VALUE is P -complete.
Proof As shown in Problem 2.12 , every Boolean function can be realized with just AND
and OR gates (this is known as dual-rail logic) if the values of input variables and their
complements are made available. We reduce an instance of CIRCUIT VALUE to an instance
of MONOTONE CIRCUIT VALUE by replacing each gate with the pair of monotone gates
described in Problem 2.12 . Such descriptions can be written out in log-space if the gates in
the monotone circuit are numbered properly. (See Problem 8.20 .) The reduction must also
write out the values of variables of the original circuit and their complements.

The class of P -complete problems is very rich. Space limitations require us to limit our
treatment of this subject to two more problems. We now show that LINEAR INEQUALITIES
described below is P -complete. LINEAR INEQUALITIES is important because it is directly re-
lated to LINEAR PROGRAMMING , which is widely used to characterize optimization problems.
The reader is asked to show that LINEAR PROGRAMMING is P -complete. (See Problem 8.21 .)

LINEAR INEQUALITIES
Instance: An integer-valued m

n matrix A and column m -vector b .
Answer: “Yes”ifthereisarationalcolumn n -vector x > 0 (all components are non-negative
and at least one is non-zero) such that A x

×

≤ b .

We show tha t LINEAR INEQUALITIES is P -hard, that is, that every problem in P can be
reduced to it in log-space. The proof that LINEAR INEQUALITIES is in P , an important and
difficult result in its own right, is not given here. (See [ 165 ].)
THEOREM 8.9.2 LINEAR INEQUALITIES is P -hard.
Proof We give a log-space reduction of CIRCUIT VALUE to LINEAR INEQUALITIES .That
is, we show that in log-space an instance of CIRCUIT VALUE can be transformed to an in-
stance of LINEAR INEQUALITIES so that an instance of CIRCUIT VALUE is a “Yes” instance
if and only if the corresponding instance of LINEAR INEQUALITIES is a “Yes” instance.
The log-space reduction that we use converts each gate and input in an instance of a
circuit into a set of inequalities. The inequalities describing each gate are shown below. (An
equality relation a = b is equivalent to two inequality relations, a

a .) The
reduction also writes the equality z = 1fortheoutputgate z . Since each variable must
be non-negative, this last condition insures that the resulting vector of variables, x , satisfies
x > 0 .

≤ b and b ≤