R>R. Garey and myself in our book Computers and Intractability: A Guide to the Theory
of NP-Completeness, W. H. Freeman & Co., New York, 1979 (hereinafter referred to as
[G&J]; previous columns will be referred to by their dates). A background equivalent
to that provided by [G&J] is assumed, and, when appropriate, cross-references will be
given to that book and the list of problems (NP-complete and harder) presented there.
Readers who have results they would like mentioned (NP-hardness, PSPACE-hardness,
polynomial-time-solvability, etc.) or open problems they would like publicized, should
send them to David S. Johnson, Room 2C-355, AT&T Bell Laboratories, Murray Hill, NJ
07974 (or to dsj@btl.csnet). Please include details, or at least sketches, of any new
proofs; full papers are preferred. If the results are unpublished, please state explicitly that
you are willing for them to be mentioned. Comments and corrections are also welcome.
For more details on the nature of the column and the form of desired submissions, see the
December 1981 issue of this Journal.
1. C
OMPUTING WITH
O
NE
H
AND
T
IED BEHIND
Y
OUR
B
ACK
As a result of my six-month absence from these pages, I find that I have been
scooped! While I was away, Dr. Crypton of Science Digest was busy interview-
ing all my sources, and now has beaten me into print by at least three months.
His March 1986 column [18] provides an informative introduction to the topics I
will be covering, as well as large color pictures of two of the protagonists, quo-
tations from several others, and only one or two technical misunderstandings.
Our mutual subject is the recent spate of exciting new lower bound results.
Although there continues to be a slow trickle of papers with provocative titles
like P = NP or P
NP (at least one of each is currently in circulation),
none has yet been found to lack its own one or two technical misunderstand-
ings. If we believe that P
NP and restrict ourselves to the realm of verified
proofs, there remains a substantial gap between the superpolynomial lower
bounds we would like to prove and the lower bounds we have so far been able
to prove for general models of computation. For instance, in the circuit com-
plexity model the best lower bound known for a problem in NP has only - 2 -
increased from
2.5n
to
3n
since [G&J] was published seven years ago [9].
Many researchers have thus turned their attention to machine models whose
computational power is sufficiently limited that superpolynomial lower bounds
may be easier to prove. Such a lower bound would imply only that the problem
at hand is hard when your machine has one hand tied behind its back, but the
techniques and insights developed might eventually be of use in attacking more
general models. In any case, the mathematics involved offers its own chal-
lenges and rewards. This column will cover three popular ways of restricting
the general Boolean circuit model and the surprising new developments that
have recently occurred relating to each.
Section 2 considers the restriction to monotone circuits, i.e., circuits having
only
/
/\\//\\
and
\
\//\\//
(and and or) gates, with no
� (not) gates allowed. I will
discuss key new results of A. A. Razborov [37,38], as well as recent improve-
ments by others and some historical sidelights. Section 3 is devoted to circuits
of bounded depth, where Andy Yao [53] is the source of the recent break-
through (and where both Dr. Crypton and I were scooped by Gina Kolata in Sci-
ence [27]). The bounded-depth circuit model is especially interesting because
of its connection to questions about relativized versions of the polynomial hier-
archy, and Yaos results resolve two long-standing open problems in this area.
Section 4 considers fixed width branching programs, a generalization of
bounded depth circuits and another hotbed of lower-bound research. Here Da-
vid Barrington [6] has greatly upset expectations by showing that a supposedly
infinite hierarchy has at most five levels. In a brief concluding section, I say a
few words about where these new results seem to be taking us, and what, if
anything, they suggest about the quest for a proof that P
NP.
2. M
ONOTONE
C
IRCUIT
C
OMPLEXITY
When theoreticians speak of circuit complexity, they normally refer to
feedback-free (combinational) circuits in which the circuit elements are 2-
input
/
/\\//\\
gates, 2-input
\
\//\\//
gates, and 1-input
� gates, and where arbitrary fan-out is
allowed from each gate (as well as from each input). The size of such a circuit
is the number of circuit elements it contains. The circuit complexity
c( f )
of a
Boolean function
f
is the size of the smallest circuit that computes
f
.
We extend this definition to the traditional decision problems of complexity
theory, which are defined for instances of arbitrary size, as follows. Suppose
X
is such a problem, and assume that its instances are encoded as binary strings.
Let
X
n
be the restriction of
X
to inputs of length precisely
n
. Note that each
X
n
is
a Boolean function and so
c(X
n
)
is defined for each
n
. The circuit complexity of
X
is simply
c(X
n
)
viewed as a function of
n
. (See [39] for a more detailed intro-
duction to circuit complexity.)
It is easy to show that membership in P implies polynomial circuit complex-
ity. The converse is false, however, as the circuits that realize the
c(X
n
)
lower - 3 -
bounds might not be uniform enough to be constructed efficiently. (Observe
that even undecidable problems can have polynomial circuit complexity.) Thus
showing that a problem has super-polynomial circuit complexity may well be
more difficult than merely showing that the problem is not in P. It is a natural
approach to try, however. Unfortunately, although counting arguments show
that almost all Boolean functions on
n
variables have circuit complexity expo-
nential in
n
[42], the best bound we know for a problem in NP is the
3n
bound of
[9] mentioned above.
(Exponential bounds are known for problems not in NP, however. The first
such result was proved in 1967 by Ehrenfeucht [19], and was for the problem of
identifying the true sentences in the theory of integer arithmetic with all quanti-
fiers bounded by constants in iterated exponential form (e.g.,
3
2
5
). Meyer gener-
alized this, observing that exponential lower bounds on circuit complexity hold
for any problem that is EXPSPACE-hard (under polynomial transformations
that increase length at most linearly) [32]. Specializing to a fixed input size,
Stockmeyer in [46] constructed a particular 3696 variable Boolean function with
circuit complexity at least
10
123
.)
Given our lack of success in proving even superlinear lower bounds on the
circuit complexity of problems in NP, researchers wishing to prove superpoly-
nomial bounds have turned to the study of less powerful variants on the general
Boolean circuit model. Note that, just as the class P is immune to reasonable
changes in the underlying machine model, the class of problems that have poly-
nomial circuit complexity is immune to reasonable changes in the set of al-
lowable circuits. For instance, we might limit fan-out by restricting it to a new
circuit element that fans out a single input to two outputs, or we might re-
place the
/
/\\//\\
,
\
\//\\//
, and
� gates by some other finite complete basis for Boolean logic.
Monotone circuit complexity arises from an unreasonable restriction on
the model.
The monotone circuit complexity
c
m
( f )
of a function
f
is the size of the small-
est circuit that computes
f
and contains only
/
/\\//\\
and
\
\//\\//
gates. We call such circuits
monotone because changing an input to a circuit element from 0 to 1 can
never change the value of that elements output from 1 to 0. Monotone circuits
are unreasonable because
/
/\\//\\
s and
\
\//\\//
s do not by themselves form a complete
basis, i.e., not all Boolean functions can be computed by monotone circuits.
Only monotone functions can be computed, functions whose value can never
be turned from 1 to 0 by changing an input variable from 0 to 1. (As a simple
example of a non-monotone Boolean function, consider the parity function,
which has value 1 if and only if an odd number of its inputs are 1.)
Fortunately, there are some interesting and non-trivial monotone problems. In
particular, consider the NP-complete problem of determining whether a graph
G
= (V,E)
has a clique (i.e., complete subgraph) of size
| V| /2
. Suppose instances
are encoded as the lower triangle of the adjacency matrix of the graph, i.e., with
one variable for each of the
| V| (| V| 1)/2
potential edges in the graph. Then the - 4 -
problem is monotone, since adding an edge to a graph can never decrease the
size of the largest clique.
It was in connection with this problem that monotone circuit complexity first
became linked to NP-completeness. The year was 1973, and the occasion was a
suggestion by C. P. Schnorr [40] of a potential method for proving P
NP. It
depended on the observation that P
NP is jointly implied by the following two
plausible conjectures:
(a) If a monotone problem has superpolynomial monotone circuit complexity,
then it has superpolynomial general circuit complexity.
(b) Monotone circuits that test whether a graph has a clique of size
| V| /2
must
have sizes that grow superpolynomially in
n
.
Neither conjecture could be proved at the time, and they have remained open
for over a decade. Doubts about (a) were expressed early, however, and re-
ceived added impetus from a 1979 result of Valiant concerning monotone and
non-monotone computations in arithmetic. The arithmetic analogues of
/
/\\//\\
,
\
\//\\//
, and
� gates are the operations of
�
,
+
, and , i.e., multiplication, addition, and sub-
traction. (A more precise analogue for
� would be