Chapter 

Computational Complexity 

DB Shmoys and E Tardos 

School of Operations Research and Industrial Engineering 

Cornell University Ithaca NY USA 

􀀀January 

Complexity of Computational Problems 

Shades of Intractability 

Living with Intractability 

Inside P 

Computational complexity theory attempts to understand the power of computation	 by providing 
insight i n to the question why certain computational problems appear to be more di
cult than 
others Computation has added a dimension to the study of combinatorics The theorem that	 
given a matching in a graph	 there exists a larger matching if and only if there is an augmenting 
path	 is not the complete answer is it possible to eciently construct a larger matching if one 
exists Although such an algorithm is known for the matching problem	 this is not the case for 
many c o m binatorial problems Indeed	 the greatest challenge confronting complexity theory is to 
provide techniques to prove that no e 
cient algorithm exists for a given problem 

Computational complexity theory provides the mathematical framework in which to discuss 
these questions	 and while substantial progress has been made towards distinguishing the di
culty 
of computational problems	 most of the basic issues remain unresolved In this chapter	 we will 
describe the fundamentals of this theory and give a brief survey of the results that have b e e n 
obtained in its rst quarter century For a more detailed and complete exposition	 the reader is 
referred to the textbooks by Garey Johnson and Hopcroft Ullman as well as to 
the more recent Handbook of Theoretical Computer Science edited by v an Leeuwen 

Complexity of Computational Problems 

In this section	 we will outline the essential machinery used to give formal meaning to the 
complexity of computational problems This involves describing what is precisely meant b y a 
computational problem	 setting up a mathematical model of computation	 and then formalizing 
the notion of the computational resources required for a problem with respect to that model 
Unfortunately there is no one standardized speci
cation in which to discuss these questions For 
this theory to produce meaningful results	 it is essential that the de
nitions be robust enough so that 
theorems proved with respect to them apply equally to all reasonable variants of this framework 


Indeed	 the particular de
nitions that we will rely on will be accompanied by evidence that these 
notions are su
ciently exible 

Computational problems 

Computation can be thought of as nding a suitable output for a given input Therefore	 a 
computational problem is speci
ed by a relation between inputs and output an algorithm to 
solve the problem takes an acceptable input	 called an instance and computes an output that 
satis
es the inputoutput relation for example	 given a directed graph	 output a Hamiltonian 
circuit	 if there is one	 and otherwise indicate that none exists This framework is very general	 
and we will focus attention on certain sorts of inputs and outputs 

The most common type of input 􀀀or output is a string of characters over a 
nite alphabet 
The previous example can be cast in this setting	 since it is easy to represent a graph of order n as 
such a string of s and s one might concatenate the rows of the nn matrix Aaij where 
aij if and only if ij is an arc Alternatively 	o n e m i g h t list the names of the nodes incident 
from node i 	fo r in where the node named j is encoded by the binary representation of 
j Observe that the second representation will be more compact if the graph has few arcs	 but 
this dierence is limited	 in that the length of the input in one format is at most the square of the 
length in the other 

Some combinatorial structures cannot be compactly represented as a string for example	 a 
matroid on n elements is most naturally represented by a string of length 
n where each c haracter 
indicates whether a particular subset is independent In such cases	 it is customary to use an oracle 
to specify the input the algorithm may write down queries	 such as a particular subset to be tested 
for independence	 and the oracles answer may be used in the next step of the algorithm Sometimes	 
there is no natural 
nite representation of the input	 such as in the problem of optimizing over a 
convex body For this example	 one standard way t o g i v e the input is via an oracle that decides 
whether a given point i s i n t h e b o d y and if not	 outputs a separating hyperplane For any oracle	 
there is an associated parameter which is used as a measure of the size of the input 

In analyzing algorithms	 we often view numbers as atomic units	 without regard for their lengths	 
and so an input can also be a list of numbers	 where the size of the input is the number of elements 
in the list However	 for the remainder of this chapter we will focus on inputs that are strings	 
although it is straightforward to extend the discussion of computational models and complexity t o 
include these alternatives 

An important special case of a computational problem is a decision problem where the 
output is restricted to either yes or no	 and for each input	 there is exactly one related output 
The set L of yes instances for a decision problem is often called the language associated with 
this problem A decision version of the previous example is given a directed graph	 does it contain 
a Hamiltonian circuit This type of problem will play a central role in our discussion	 and it is 
important to realize that it is not a signi
cant limitation to focus on it For example	 it is possible 
to answer the rst search version of the Hamiltonian circuit problem as follows for each arc in 
the graph	 delete the arc	 decide if the resulting graph is still Hamiltonian and replace the arc only 
in the case that the answer is no At the end of this procedure	 the remaining graph is a circuit 
Thus	 we h a ve s h o wn that 
nding a circuit is not much harder than the decision problem	 and this 
relationship remains true for all wellformulated decision versions of search problems 

Another important t ype of computational problem is an optimization problem for example	 


given a directed graph G andtwo nodes s and t 	w e m a y wish to 
nd the shortest path from s 
to t 􀀀or merely 
nd the length We shall rather treat these as decision problems by adding a 
bound b to the instance	 and	 for example	 asking whether G has a path from s to t of length at 
most b B y using a binary search procedure that iteratively halves the range of possible optimal 
values	 we see that an optimization problem can be solved with only somewhat more work than 
the corresponding decision problem 

Throughout this chapter	 we will be dealing with computational problems involving a variety 
of structures	 and we will not be specifying the nature of the encodings used We will operate 
on the premise that any reasonable encoding produces strings of length that can be bounded by 
a polynomial of the length produced by a n y other encoding When encoding numbers 􀀀which w e 
will assume to be integral there is an important distinction between the binary representation	 
which w e w i l l t ypically use	 and the unary representation eg representing as Notice 
that the latter could be exponentially bigger than the former	 and thus size is a deceptive measure	 
since it makes instances of the problem larger than they need be As we survey the complexity o f 
computational problems that involve n umb e r s w e will see that some are sensitive t o t h i s c hoice of 
encodings	 whereas others are less aected 

Models of computation and computability 

We next turn our attention to de
ning a mathematical model of a computer In fact	 we will 
present three dierent models	 and although their super
cial characteristics make them appear 
quite dierent	 they will turn out to be formally equivalent The rst of these is the Turing 
machine	 which is an extremely primitive model	 and as a result	 it is easier to prove results about 
what cannot be computed within this model On the other hand	 its extreme simplicity makes it 
illsuited for algorithm design As a result	 it will be convenient t o h a ve an alternative m o d e l t h e 
random access machine 􀀀RAM	 within which to discuss algorithms 

The name	 Turing machine	 is a slight misnomer	 since a Turing machine is a mathematical 
formulation of an algorithm	 rather than a machine A T uring machine MQ qA is 
a m a c hine that has a nite main memory represented by a 
nite set of states Q a readonly 
input tape	 a nite set of work tapes each of which c o n tains a countably in
nite number of cells 

􀀀corresponding to the integers to store a character from a nite alphabet which at least includes 
the input alphabet fg and a blank symb o l B F oreach o f th e k work tapes and the input tape 
there is a head that can read one cell of the tape at a given time	 and will be able to move 
cellbycell across the tape as the computation proceeds Throughout the computation	 the heads 
will read the contents of cells	 and depending on what was read and the current state of the main 
memory rewrite the cells and then move e a c h h e a d b y one cell	 either left or right	 as well as cause 
a c hange in the state of the main memory The basic step of a Turing machine	 a transition 	is 
modeled by a partial function 

Q 
k Q 
k f LRg 
k 

that selects the new state	 the contents of the cells currently scanned on the work tapes	 and 
indicates the direction in which e a c h h e a d m o ves one cell as a deterministic function of the 
current state and the contents of the input and work tape cells currently being read One may view 
the transition function as the program hardwired into this primitive m a c hine The computation is 
begun in state q with the input head at the left end of the input	 and all of the work tapes and 
the rest of the input tape blank The machine halts if is unde
ned for the current state and 


the symbols read An input is accepted if it halts in a state in the accepting state set AQ A 
Turing machine M solves a decision problem L if L is the set of inputs accepted by M and M halts 
on every input such a language L is said to be decidable This de
nition of a Turing machine 
is similar to the one given by T uring and the reader should note that many equivalent 
de
nitions are possible 

We h a ve de
ned a Turing machine so that it can only solve decision problems	 but this de
nition 
can be easily extended to arbitrary computational problems by for example	 adding a writeonly 
output tape	 on which t o p r i n t the output before halting Although this appears to be a very 
primitive form of a computer	 it has become routine to accept the following proposition 

Churchs Thesis A n y function computed by an e ective procedure can be computed by a T uring 
machine 

Although this is a thesis in the sense that any attempt to characterize the inexplicit notion 
of eective procedure would destroy i t s i n tent	 it is supported by a host of theorems since for 
any k n o wn characterization of computable functions	 it has been shown that these are Turing 
computable 

A random access machine 􀀀RAM is a model of computation that is wellsuited for specifying 
algorithms	 since it uses an idealized	 simpli
ed programming language that closely resembles the 
assembly language of any modernday digital computer There is an in
nite number of memory 
cells indexed by t h e i n tegers	 and there is no bound on the size of an integer that can be stored 
in any cell A program can directly specify a cell to be read from or written in	 without moving a 
head into position Furthermore	 there is an indirect addressing option	 that uses the contents of 
a cell as an index to another cell that is then 􀀀seemingly randomly accessed All basic arithmetic 
operations can be performed For further details on RAMs the reader is referred to Aho	 Hopcroft 

Ullman 

Another model of computation closely tied to a practical setting is the logical circuit model 
The simplicity of the circuit model makes it extremely attractive for proving lower bounds on 
the computational resources needed for particular functions	 and research along these lines will be 
discussed in depth in Chapter A circuit may be thought of as a directed acyclic graph	 where the 
nodes of indegree are the Boolean input gates 􀀀that can assume value or and the remainder 
correspond to functional gates of the circuit and are labeled with an operation	 such as the logical 
or negation	 or logical and operations The nodes of outdegree are the outputs A g i v en circuit 
only handles inputs of a particular size	 and so we specify a circuit for each input length We s a y 
that the family of circuits solves a computational problem if for each input the corresponding circuit 
in the family generates a related output Note that this model diers from the previous two	 in 
that the circuit for inputs of length n can be tailored nonuniformly to the particular value of n 
whereas a Turing machine or a RAM must run on inputs uniformly independent of their length 
We can make the notion of a family of circuits equivalent to the other models of computation by 
insisting that there be a Turing machine that	 on input n computes the description of the circuit 
for inputs of length n 

In spite of the apparent dierences in these three models	 any particular choice is one of conve 
nience	 and not of substance 


Theorem The following classes of problems are identical 

the class of computational problems solvable by a T uring machine 

the class of computational problems solvable by a R A M 

the class of computational problems solvable by a family of circuits that can be generated by 
a T uring machine 

Theorem is complemented by the following theorem	 which is a consequence of the fact 
that there are an uncountable number of decision problems	 but only a countable numb e r o f T uring 
machines 

Theorem Not all decision problems are solvable by a T uring machine 

The understanding of this inherent limitation on the power of computation was an outgrowth 
of results in mathematical logic In particular	 the rst incompleteness theorem of Godel 
contained the 
rst sort of undecidability result and provided many of the essential ideas that would 
be used by C h urch	 Post and Turing in their groundbreaking work on the nature of computation In 
particular	 Turing proposed what we call a Turing machine	 and this enabled the discussion 
to be conveniently directed towards computation 

At the core of all of these results is Godels notion of encoding theorems as strings in some 
uniform way Analogously 	a T uring machine can be encoded as a string by 
rst specifying the 
number of states that the machine has	 followed by a list of all of the allowed transitions Each 
such string can also be interpreted as an integer by using a binary encoding Thus	 each i n teger i 
represents a Turing machine Mi T uring showed that the language Lhp fi j Mi halts on input igis not solvable by a T uring machine His proof that this halting problem is undecidable uses 
the following diagonalization argument Suppose that Lhp were solvable by a T uring machine M 
Build another machine M that 
rst uses M to decide if the input iLhp if it is	 then M enters 
an in
nite loop	 and if not	 M halts Of course	 M must be Mk for some integer k B ut M and 
Mk cannot accept the same language	 since M halts on k if Mk does not	 and vice versa 

A problem L 􀀀manyone reduces to a problem L if there exists a function f computable 
by a T uring machine such that xL if and only if fx L Note that if L is undecid 
able and L reduces to L then L must also be undecidable This provides a strategy for 
proving additional undecidable problems As a simple example	 consider the language Le 
fi j Mi accepts on an empty inputg It is a simple exercise to convert the description of a given 
Turing machine Mi to the description of another rather trivial machine MMj that on every 
input	 
rst runs Mi with input i and accepts if Mi halts on i Clearly Mj accepts an empty input 
if and only if Mi halts on i 

A similar strategy can be used to prove G odels undecidability theorem in the context of Turing 
computability although the details of the reduction are more involved The theory of arithmetic 
for nonnegative i n tegers with addition and multiplication can be de
ned as follows Consider 
rst 
order formulas that can be constructed from variables and the constants and with the logical 
connectives and along with the operations and the binary relations and 


A sentence is a formula in which a l l o f t h e v ariables are bound We consider the standard model 
of number theory 􀀀as de
ned by t h e P eano axioms A sentence is provable if it can be deduced 
from these axioms The theory of arithmetic La Z O is the collection of provable 
sentences A relatively straightforward construction shows that Le reduces to La which yields the 
following fundamental result 

Theorem La is undecidable 

This theorem implies the incompleteness of this model of number theory ie there are sentences 
such that neither it nor its negation is provable Every complete model is decidable	 since a Turing 
machine can generate all possible deductions and stop if either the statement or its negation is 
proved 

These results were only the 
rst steps in a rich area of research that can be viewed as the 
ancestor of modernday complexity theory One of its pinnacles of achievement is the solution of 
Hilberts tenth problem	 which a s k ed for a procedure to decide if a given multivariate polynomial 
has an integervalued root Culminating years of progress in this area	 Matijasevic proved that this 
problem is undecidable 􀀀For an introduction to this history and the many results on which this 
proof builds	 the reader is referred to the survey of Davis 

An important generalization of a Turing machine that will play a fundamental role in complexity 
theory is that of a nondeterministic Turing machine Here	 the transition function is no longer 
a function	 but rather a relation	 in that at each step there is a 
nite set of possible next moves 
of which exactly one is made The notion of acceptance by a nondeterministic Turing machine 
is central to its de
nition an input is accepted if there exists a sequence of transitions of that 
cause the machine to halt in an accepting state A nondeterministic Turing machine M solves a 
decision problem L if L is the set of inputs accepted by M and for every input M halts on each 
sequence of transitions An equivalent formulation is to think of a nondeterministic Turing machine 
as a deterministic Turing machine with an additional guess tape that is a readonly tape where 
the head only moves to the right The contents of the guess tape are magically constructed and 
presented to the machine as it begins the computation For simplicity 	w e shall assume that the 
machine makes the same number of transitions for any guess The set of inputs in L is the set 
of inputs for which there is a guess that allows the machine to halt in an accepting state Note 
that a nondeterministic Turing machine accepting L can be converted into a deterministic machine 
for L by trying all of the exponentially many guesses We can view a particular computation as 
proving 􀀀or disproving the theorem	 xL in this context	 the dierence between determinism 
and nondeterminism is analogous to the dierence between proving a theorem and verifying its 
proof 

Consider again the Hamiltonian circuit problem A nondeterministic Turing machine for it 
might be constructed by letting the guess tape encode a sequence of n nodes of the graph The 
Turing machine simply veri
es that there is an arc between each consecutive pair of nodes in the 
guessed sequence	 as well as between the 
rst and last nodes If the graph is Hamiltonian	 then 
there is a correct guess	 but otherwise	 for any sequence of n nodes there will be some pair that is 
not adjacent The correct guess	 in essence the Hamiltonian circuit	 is a certi	cate that the graph 
is Hamiltonian Observe that this de
nition is onesided	 since the requirements for instances in L 
and not in L are quite dierent 


Computational resources and complexity classes 

Now t h a t w e h a ve mathematical formulations of both problems and machines	 we can describe 
what is meant b y the computational resources required to solve a certain problem 

In considering the execution of a deterministic Turing machine	 it is clear that the numb e r o f 
transitions before halting corresponds to the running time of the machine on a particular input In 
discussing the running time of an algorithm	 within any of the models	 we do not want to simply 
speak of particular instances	 and so we m ust make some characterization of the running time for 
all instances The criterion that we will focus on for most of this chapter is the worstcase running 
time as a function of the input size When we s a y t h a t a T uring machine takes n steps	 this 
means that for any input of size n 	t h e T uring machine always halts within n transitions Unless 
otherwise speci
ed	 we will let n jxj denote the length of the input string x 

We will not be interested in the precise count of the number of transitions	 but rather in 
the order of the running time A function fn is Ogn if there are constants N and c such 
that for all n N fn cgn Thus	 rather than say that a Turing machine has worstcase 
running time nn we saysimply that it is On This simpli
cation makes it possible to 
discuss complicated algorithms without being overwhelmed by details Furthermore	 for any T uring 
machine with superlinear running time and any constant c there exists another Turing machine to 
solve the same problem that runs c times faster than the original	 that can be constructed by u s i n g 

an expanded work tape alphabet 
We will also use a notation analogous to O 
g n if there are constants N and c such that 
g n if it is both O g n and g n 
to indicfor all n 
ate lN f 
ower bounds 
n cg n 
A function f 
A function f 
n 
n 
i 
i 
s 
s 

For a nondeterministic Turing machine	 we de
ne the running time to be the number of transi 
t i o n s i n a n y computation path generated by the input 􀀀Recall that we added the restriction that 
all computation paths must have the same length For a circuit	 we will want t o c haracterize the 
number of operations performed as a measure of time	 so that the relevant parameter is the size 
of the circuit	 which is the order of the graph representing it For a RAM	 there are two standard 
ways in which t o c o u n t the running time on a particular input In each operation	 a RAM can	 for 
example	 add two n umbers of unbounded length In the unit
cost model	 this action takes one 
step	 independent of the lengths of the numbers being added In the log
cost model	 this operation 
takes time proportional to the lengths of the numbers added These measures can have radically 
dierent v alues Take and repeatedly square it k times With each squaring	 the numb e r o f 
bits in the binary representation essentially doubles Thus	 although we h a ve taken only k steps 
in the unitcost model	 the time required according to the logcost model is exponential in k This 
may seem arti
cial	 but this problem can occur	 for example	 in Gaussian elimination	 if it is not 
implemented carefully Technically 	w e will use the logcost model	 in order to ensure that the 
RAM is equivalent t o t h e T uring machine in the desired ways But	 when speaking of the running 
time of an algorithm	 it is traditional to state the running time in the unitcost model	 since for all 
standard algorithms one can prove that the pathological behavior of the above example does not 
come into play 

Time is not the only computational resource in which w e will be interested we will see that 
the space complexity of certain combinatorial problems gives more insight i n to the structure of 
these problems In considering the space requirements	 we will focus on the Turing machine model	 


and will only count t h e n umber of cells used on the work tapes of the machine Furthermore	 we 
will again be interested in the asymptotic worstcase analysis of the space used As was true for 
time bounds	 the space used by a T uring machine can be compressed by a n y constant factor The 
space used by a nondeterministic Turing machine is the maximum space used on any computation 
path For circuits	 it will also be interesting to study their depth the longest path from a node of 
indegree to one of outdegree 

The notion of the complexity of a problem is the order of a given computational resource	 
such as time	 that is necessary and su
cient to solve the problem Consider the following directed 
reachability problem given a directed graph G 	a n d t wo speci
ed nodes s and t does there exist 
a path from s to t When we s a y that the complexity of the directed reachability problem for a 
graph with m arcs is m this means that there is a unitcost RAM algorithm that has worst 
case running time Om and there is no algorithm with running time of lower order Tight results of 
this kind are extremely rare	 since the tremendous progress in the design of e 
cient algorithms has 
not been matched	 or even approached	 by the slow progress in techniques for proving lower bounds 
on the complexity of these problems in general models of computation For example	 consider the 


colorability problem given an undirected graph G with m edges	 can the nodes be colored 
with three colors so that no two adjacent nodes are given the same color ie 	is G The 
best lower bound is only m in spite of substantial evidence that it cannot be solved in time 
bounded by a polynomial 

In order to study the relative p o wer of particular computational resources	 we i n troduce the 
notion of a complexity class which is the set of problems that have a speci
ed upper bound on 
their complexity It will be convenient to de
ne the complexity c l a s s D TIM E Tn to be the set 
of all languages L that can be recognized by a deterministic Turing machine within time OT n 
N TIM E Tn denotes the analogous class of languages for nondeterministic Turing machines 
Throughout this chapter	 it will be convenient to make certain assumptions about the sorts of time 
bounds that de
ne complexity classes A function Tn is called fully time
constructible if there 
exists a Turing machine that halts after exactly Tn steps on anyinput oflength n All common 
time bounds	 such a s n log n or n are fully timeconstructible We will implicitly assume that any 
function Tn used to de
ne a timecomplexity class is fully timeconstructible 

The single most important complexity class is P the class of decision problems solvable in 
polynomial time Two of the most wellknown algorithms	 the Euclidean algorithm for 
nding the 
greatest common divisor of two i n tegers and Gaussian elimination for solving a system of linear 
equations	 are classical examples of polynomialtime algorithms In fact	 Lame observed as early 
as that the Euclidean algorithm was a polynomialtime algorithm In Von Neumann 
contrasted the running time for an algorithm for the assignment problem that turn#ed$ out #to be$ 
a moderate power of n ie considerably smaller than the %obvious estimate n for a complete 
enumeration of the solutions Edmonds and Cobham were the 
rst to introduce P as 
an important complexity class	 and it was through the pioneering work of Edmonds that polynomial 
solvability became recognized as a theoretical model of e 
ciency With only a few exceptions	 the 
discovery of a polynomialtime algorithm has proved to be a important rst step in the direction 
of 
nding truly e
cient algorithms Polynomial time has proved to be very fruitful as a theoretical 
model of e
ciency both in yielding a deep and interesting theory of algorithms and in designing 
e
cient algorithms 

There has been substantial work over the last years in 
nding polynomialtime algorithms 


for combinatorial problems It is a testament to the importance of this development that much o f 
this handbook is devoted to discussing these algorithms This work includes algorithms for graph 
connectivity and network ow see Chapter for graph matchings 􀀀see Chapter for matroid 
problems 􀀀see Chapter for point lattice problems 􀀀see Chapter for testing isomorphism 􀀀see 
Chapter for 
nding disjoint paths in graphs 􀀀see Chapter as well as for problems connected 
with linear programming 􀀀see Chapters and 

Another	 more technical reason for the acceptance of P as the theoretical notion of e
ciency 
is its mathematical robustness Recall the discussion of encodings where we r e m a r k ed that any 
reasonable encoding will have length bounded by a polynomial in the length of another As a 
result	 any polynomialtime algorithm which expects its input in one form can be converted to a 
polynomialtime algorithm for the other In particular	 note that the previous discussion of the two 
dierent encodings of a graph can be swept aside and we can assume that the size of the input for 
a graph of order n is n Notice further that the informal de
nition of P given above does not rely 
on any model of 􀀀deterministic computation One justi
cation for this statement is the following 
theorem 

Theorem The following classes of problems are identical 

the class of computational problems solvable by a T uring machine in polynomialtime 

the class of computational problems solvable by a RAM in polynomialtime under the logcost 
measure 

the class of computational problems solvable by a family of circuits of polynomial size where 
the circuit for inputs of size n can be generated by a T uring machine with running time 
bounded by a polynomial in n 

The importance of the class NP k NTIME nk is due to the wide range of important 
problems that are known to be in the class	 and yet are not known to lie in P F or example	 the 
nondeterministic algorithm given for the Hamiltonian circuit problem is clearly polynomial	 and so 

this problem lies in N P H o wever	 it is not known whether this	 or any p r o b l e m i s i n N P n P and 
this is	 undoubtably the central question in complexity theory 
Open Problem Is P N P 
The following reformulation of N P is often useful L N P if there exists a language L P and 

a polynomial pn such that xL y such that jyj p jxj and xy L 􀀀We will denote 
this polynomially bounded quanti
cation by p 

For each decision problem L there is a complementary problem	 L 	s u c h as the problem of 
recognizing nonHamiltonian graphs For any complexity class S 	le t co S denote the class of 
languages whose complement i s i n S The de
nition of P is symmetric with respect to membership 
and nonmembership in L so that P co P NP is very dierent in this respect In fact	 it is 
unknown whether the Hamiltonian circuit problem is in co NP 

Open Problem Is NP co NP 

Edmonds brought attention to the class NP co NP and called problems in this 
class well
characterized since there is both a short certi
cate to show that the property holds	 


as well as a short certi
cate that it does not Edmonds was working on algorithms for nonbipartite 
maximum matching at the time	 and this problem serves as a good example of a problem in this 
class If the instance consists of a graph G and a bound k andwe w ish to knowif thereis a 
matching of size at least k the matching itself serves as a certi
cate for an instance in L whereas 
an oddset cover serves as a certi
cate for an instance not in L 􀀀see Chapter Note that there 
is a minmax theorem characterizing the size of the maximum matching that is at the core of the 
factthatmatch in g is in NP co NP and indeed minmax theorems often serve this role As 
mentioned above	 matching is known to be in P and this raises the following question 

Open Problem Is P NP co NP 

We will also be concerned with complexity classes de
ned by the space complexity of problems 
As for time	 let DSPACE Sn and N SPACE Sn denote	 respectively the class of lan 
guages accepted by deterministic and nondeterministic Turing machines within space OSn We 
will implicitly assume the following condition for all space bounds used to de
ne complexity classes 
a function Sn is fully space
constructible if there is a Turing machine that	 on any input of 
length n delimits Sn tape cells and then halts Three space complexity classes will receive t h e 
most prominent a t t e n tion 

L D SPACE 􀀀log n 

NL N SPACE 􀀀log n and 

PSPA CE kDSPACE nk 

One might be tempted to add a fourth class	 N PSPACE but we shall see that nondeterminism 
does not add anything in this case We will see that the chain of inclusions 

L NL P NP PSPACE 

holds	 and the main thrust of complexity theory is to understand which of these inclusions is proper 
At the extremes	 a straightforward diagonalization argument due to Hartmanis	 Lewis Stearns 
shows that L PSPACE and a result of Savitch further implies that N L PSPACE but after 
nearly a quarter century more work	 these are the only sets in this chain known to be distinct 

Randomized computation 

In this subsection	 we will consider models of computation that exploit the power of randomiza 
tion in the design and analysis of algorithms without making probabilistic assumptions about the 
inputs A randomized algorithm is an algorithm that can ip coins during the computation that 
is	 we consider a 
xed input	 and study the algorithms behavior as a random variable depending 
only on the coin ips used For the algorithms discussed below	 the algorithm is allowed to make 
mistakes	 but for each input the probability of error must be very small 

The most wellknown randomized algorithm is for testing primality I n t h e primality testing 
problem 	w e are given a natural numb e r N 	a n d w e wish to decide if it is prime It is not 
known whether primality testing is in P The input size of the numb e r N is log N and therefore 
algorithms that simplistically search for divisors of N do not run in polynomial time Consider 
Fermats theorem if N is prime then aN is congruent t o a modulo N for every integer a This 
provides a way to conclude that a number is not prime without actually exhibiting a factor That 


is	 if we nd an integer a such that aN is not congruent t o a modulo N denoted aN a mod N 
then we can conclude that N is not prime 􀀀Note that aN mod N can be computed in polynomial 
time by repeatedly squaring modulo N Letsuch a n a be called a witness for N s compositeness 
The advantage of this kind of witness	 compared to exhibiting a divisor	 is that if there exists an 
integer a such that aN a mod N then at least half of the integers in the range from to N have 
this property 

Unfortunately there are composite numbers	 the socalled Carmichael numb e r s that are 
not prime	 but for which no witness exists If we momentarily forget about the existence of these 
numb e r s w e get the following algorithm for testing primality given an integer N 	c hoose an integer 
a in the range to N at random	 and check i f a is a witness for N If a witness is found	 then we 
know that N is not prime 􀀀and not even a Carmichael number On the other hand	 if N is not a 
prime and also not a Carmichael number	 then a random a is a witness with probability at least 
one half Running this test k times with independent random choices	 we either 
nd a witness or can 
fairly safely conclude that no witness exists with error probability 
k This gives a randomized 
polynomialtime algorithm to recognize the language of all primes and Carmichael numbers Rabin 
and Solovay Strassen	 by using a somewhat more sophisticated variant o f F ermats theorem	 gave 
randomized polynomialtime algorithms that accept the language of all primes 

The above idea actually gives a polynomialtime algorithm if the extended Riemann hypothesis 
is true Miller has proved that if the extended Riemann hypothesis holds	 then there exists a witness 
for N 􀀀in more or less the above sense that is at most O 􀀀􀀀log N By trying all the integers up to 
this limit	 we w ould get a polynomialtime deterministic algorithm for primality testing For more 
details on this and other numbertheoretic algorithms see the survey of Lenstra Lenstra 

The formal de
nition of a randomized Turing machine is similar to the de
nition of a 
nondeterministic Turing machine in the sense that at every point during the computation there 
could be several dierent next steps Randomized Turing machines have a readonly randomizing 
tape similar to the guess tape of the nondeterministic Turing machine We can think of this tape 
as providing the outcomes of the coin ips to be used by the algorithm We shall assume that for a 
given input length n the algorithm reads a 
xed number of bits	 fn from the randomizing tape 
The probability that the randomized Turing machine accepts an input x of length n is de
ned 
to be the fraction of all possible strings of length fn that	 when used as the initial segment o f 
the randomizing tape cause the Turing machine to accept x F or the randomized Turing machine	 
we t a k e the simplifying approach that the running time for an input is the maximum numb e r o f 
transitions in some sequence of allowed transitions ie for some contents of the randomizing tape 
Unlike the nondeterministic Turing machine	 a randomized Turing machine is not just a convenient 
mathematical model randomized algorithms can be implemented in practical settings 

We de
ne BPP the class of languages accepted by a randomized polynomialtime algorithm	 
as follows A language L is in BPP if there exists a polynomialtime randomized Turing Machine 
that accepts each xL with probability at least and rejects each xL with probability 
at least We can think of the outcomes of the computation as follows if the Turing machine 
accepts x this means that x is probably in L whereas if it rejects	 that means that x is probably 
not in L Note that the choice of the number in the de
nition was rather arbitrary if we 
run the algorithm k times independently and take the majority decision	 we can decrease the 
probability of error exponentially in k If k is fairly large	 then one can accept the answer given by 
the algorithm without any reasonable shadow of doubt 􀀀The letters BPP stand for a Probabilistic 


Polynomialtime algorithm with probabilities Bounded away from 

Other problems not known to be in P for which there is a randomized polynomialtime algorithm 
include computing the square root of an integer x modulo a prime p and deciding whether the 
determinant of a matrix whose entries are multivariate polynomials is the zero polynomial The 
algorithm for the latter problem assigns random values to the variables in the polynomials	 and 
computes the resulting determinant of numbers If this determinant is nonzero	 then certainly 
the determinant o f v ariables is nonzero as a polynomial On the other hand	 if the determinant o f 
variables is nonzero	 then a random evaluation will yield a nonzero determinant w i t h v ery high 
probability This can be used to show that given a graph G a subset of edges F and an integer k 
determining whether a graph has a perfect matching with exactly k edges in F can be solved by a 
randomized polynomialtime algorithm 􀀀see Chapter 

Notice that the randomized primality testing algorithm has a property stronger than required 
by the formal de
nition The conclusion that N is not a prime was certain uncertainty arose 
only in the case of the conclusion	 N is probably prime The complexity class RP isde
nedto 
reect this asymmetry A language L is in RP if there exists a polynomialtime randomized Turing 
Machine RM such that eachinputthat RM can accept 􀀀along any computation path is in L and 
foreach in p u t xL the probability that RM accepts x is at least Note again that the choice 

of the number is arbitrary 
The above mentioned algorithms show that primality testing is in co R P There are very few 
problems known to be in B P P but not in RP or co R P B a c h	 Miller Shallit provided the 
rst 

natural examples of problems in BPP that are not obviously in RP or co RP They proved 
that the set of perfect numbers is in BPP 􀀀A natural numb e r N is perfect if the sum of all its 
natural divisors is N for example	 is perfect 

In some sense	 an RP algorithm is more satisfying than a BPP algorithm	 since at least one 
of the two conclusions reached can be claimed with certainty A randomized algorithm that never 
makes mistakes would be even more desirable This can be de
ned in the following way an 
algorithm to compute a function fx is a Las Vegas algorithm if	 given an input x this randomized 
algorithm either correctly computes fx or it halts without coming to a conclusion	 and the 
probability of the latter outcome is less than for each input x It is easy to see that a language 
L is in RP co RP if and only if there exists a polynomialtime Las Vegas algorithm to decide 
membership in L Observe also that if we repeat any L a s V egas algorithm until it gives an answer	 
the resulting algorithm always gives the correct answer and for any input	 it is expected to run in 
polynomial time Recent results of Goldwasser Kilian and Adleman Huang yield a sophisticated 
Las Vegas algorithm for testing primality 

There is evidence that suggests that randomized polynomial time is not that dierent f r o m P 
For example	 consider a nonuniform analog of P by considering the class of languages accepted 
by a family of polynomialsize circuits Alternatively one can make t h e T uring machine model 
nonuniform	 by a l l o wing the machine free access to a prespeci
ed polynomiallength advice string 
sn when processing any input of length n This class is denoted P poly For any language L 
in BPP 	w e can assume without loss of generality that there is a machine RM that accepts each 
xL with probability 
n and rejects each xL with probability 
n 	w h ere n 
denotes the length of x 􀀀since taking the majority decision of repeated trials decreases the error 
probability exponentially However	 this implies that the probability that a random string used 


by RM for an input of length n would work correctly for all strings of length n is at least 
Thus	 there must existsuch a good string to serveas theadvice	and we have shown thefollowing 
theorem	 which is based on an idea of Adleman 

Theorem BPP P poly 

Shades of Intractability 

In this section we will consider many computational problems	 and see that the universe does 
not appear to be divided simply into tractable and intractable problems Current evidence suggests 
that there are a variety of dierent classes of problems	 each c haracterizing its own particular shade 
of intractability Much o f t h e w ork in complexity theory is aimed at understanding the correct 
framework in which to place these problems 

The subsections here reect three types of approaches for characterizing the di
culty of these 
problems The nicest sort of result places absolute limits on our ability to solve problems for 
example	 the most severe limit is to show that a problem is undecidable	 and among decidable 
problems there are only a handful that can be proven intractable	 in the sense that they require 
a certain nontrivial amount of time or space to be solved Much more common is to provide a 
completeness result to show that a particular problem is a hardest problem within a given com 
plexity class If the class contains a great number of problems not known to be solvable with more 
modest resources	 this provides evidence that the problem is intractable Finally in order to better 
understand a problem	 it has frequently been useful to strengthen the basic Turing machine model 
in order de
ne complexity classes that better characterize the problem Such an alternative view 
has often made problems appear less intractable the subsections on the polynomialtime hierarchy 
and on randomized proofs present results in this direction 

Evidence of intractability NP completeness 

The lack o f l o wer bounds with respect to a general model of computation for either space or 
time complexity has led to the search for other evidence that suggests that lower bounds hold One 
such t ype of evidence might be the implication if the Hamiltonian circuit problem is in P then 
P NP NP contains a tremendous variety of problems that are not known to be in P 	and so by 
proving such a claim	 one shows that the Hamiltonian circuit problem is a hardest problem in NP 
in that any polynomialtime algorithm to solve i t w ould in fact solve thousands of other problems 

The principal tool in providing evidence of this form is that of reduction We will say that 
a problem L polynomial
time reduces to L if there exists a polynomialtime computable 
function f that maps instances of L into instances of L such that x is a yes instance of L 
if and only if fx isa yes of L We shall denote this by L pL Notice that if there were 
a polynomialtime algorithm for L 	w e could then obtain a polynomialtime algorithm for L by 


rst computing fx and then running the assumed algorithm on fx This composite procedure 
is polynomialtime	 since the composition of two polynomials is itself a polynomial 

De	nition A problem L is NP 
complete if 

L NP 


for all L NP L pL 

The composition argument given above yields the following results 

Theorem For any NP complete problem LL P if and only if P NP 

Theorem If L is NP complete L NP and L pL then L is NP complete 

The rst result says that any NP complete problem completely characterizes NP in its rela 
tionship to P and that we can focus on any s u c h problem without loss of generality in trying to 
prove that the two classes are dierent The Hamiltonian circuit problem is NP complete	 and 
section we will prove that several combinatorial problems are among the plethora having this prop 
erty The second result gives a strategy for proving that a problem is NP complete	 provided that a 


rst NP complete problem is known Of course	 to initiate this strategy 	w e m ust show that some 
natural problem has this property and it was a landmark achievement in complexity theory when 
Cook showed that the problem of deciding the satis
ability of a formula in propositional 
logic is NP complete The importance of this result was only fully recognized through the work 
of Karp whose seminal paper showed wellknown combinatorial problems to be NP 
complete Independently Levin discovered the same approach to studying the intractability 
of computational problems 

A Boolean formula in conjunctive normal form is the conjunction and of clauses CC s 
each of w hichis adisjunction or of literals xx x t xt where each xi is a Boolean variable 
and xi denotes its negation In the satis	ability problem 􀀀SAT we are given such a Boolean 
formula	 and asked to decide if there exists a truth assignment for the variables such that the 
formula evaluates to true 

Theorem The satis ability problem is NP complete 

Proof
 It is easy to see that the satis
ability problem is in NP since we c a n i n terpret the 
rst t 
cells of the guess tape as providing the assignment	 and then it is a simple matter to evaluate the 
formula for that assignment in polynomial time 

Next	 we m ustshow th a t fo r a n ylanguage L NP there exists a polynomialtime function f 
that maps each instance x of the original problem into a Boolean formula such that xL if and 
only if fx is satis
able Before giving the reduction	 we rst argue that M may be assumed to 
have a form somewhat simpler than the original de
nition Imagine that the Turing machine has 
only one tape	 which serves both as the input tape and as the work tapes A simple construction 
shows that if there exists a nondeterministic Turing machine M with running time Tn then there 
exists a nondeterministic machine of this simpler form that 
nishes within time Tn b y enlarging 
the alphabet so that each s y m bol denotes one character on all of the tapes of M Furthermore	 
we can assume without loss of generality that for some l the machine M runs for exactly time nl 
on every input of length n 

Let M b e s u c h a simpli
ed machine that runs on input x for T steps before halting We can 
describe the con
guration of the machine at any instant of the computation by giving the contents 
of the tape	 the position of the head and the current state This can all be encoded as a string 


by using the alphabet Q fg where the 
rst coordinate gives the contents of a cell 
of the tape	 and the second is unless the head is reading that cell of the tape when it is the 
current state We can then encode the entire computation as a matrix	 where each r o w o f t h e 
matrix corresponds to one step of the computation	 and each column corresponds to a cell of the 
tape 􀀀Note that there are no more than T cells in either direction of the initial head position 
that could be reached during the computation Acceptance of x by M boils down to the following 
question does there exist a guess that causes the matrix to be 
lled in so that in the last row	 the 
con
guration contains an accepting state 

It is straightforward to construct a Boolean formula that represents this question Let gg T 
b e v ariables that represent the binary values of the guess tape Let aijk represent the contents of 
the ijth cell of the matrix in the sense that it is if and only if it contains the kth character of 

The formula will be a conjunction of pieces that correspond to the following conditions that 
we wish to impose the variables represent some matrix	 in that exactly one character is stored in 
each e n try the 
rst row corresponds to the initial con
guration for input x the last row c o n tains 
an accepting state the computation proceeds in the deterministic way speci
ed by the guesses 
gi We will not give e a c h of these in detail	 but only sketch the main ideas The 
rst is easy 
foreach of the OT e n tries	 check that at least one of the associated variables is by their 
or and for each pair	 check that not both are by the or of their negations The second and 
third are equally routine The last condition takes a bit more work and is based on a principle of 
locality if locally the computation ie the matrix appears correct	 then the entire computation 
was performed correctly In fact	 it is su
cient t o c heck t h a t e a c h submatrix appears correct 
Furthermore	 it is an easy exercise to encode that some submatrix in the ith and i st 
rows behaves according to the guess gi By taking the conjunction of all OT such pieces of local 
information	 we enforce that the computation is done correctly It is now routine to verify that 
formula constructed is satis
able if and only if there are guesses that lead M to accept x 
􀀀 


Now that w e have ourinitial NP complete problem	 we proceed to give a n umber of reductions 
to show t h a t s e v eral important c o m binatorial problems are NP complete Literally thousands 
of problems are now known to be NP complete	 so that we will only present a small handful 
of examples that serve to illustrate an important phenomenon in complexity theory or relate to 
important c o m binatorial problems discussed elsewhere in this chapter	 as well as in the rest of this 
volume Most of the problems that we consider were shown to be NP complete in the pioneering 
work of Karp 

Many restricted cases of the satis
ability problem are also NP complete One that is often used 
in further NP completeness proofs is the 
SAT problem	 where each clause of the conjunctive 
normal form must contain exactly three literals It is a simple task to show t h a t b y adding additional 
variables	 longer clauses can be broken into clauses of length three	 yielding a new formula that can 
be satis
ed if and only if the original can 

For the stable set problem 	w e are given a graph G and a bound k and asked to decide if 

Gk that is	 do there exist k pairwise nonadjacent n o d e s i n G It is easy to see that this 
problem is in NP and to show that it is complete	 we reduce 􀀀SAT to it and invoke Theorem 
Given a SAT instance 	w e construct a graph G as follows for each clause in let there be 
nodes in G 	e a c h representing a literal in the clause	 and let these nodes induce a clique ie 
they are pairwise adjacent complete the construction by making adjacent a n y p a i r o f n o d e s t h a t 
represent a literal and its negation	 and set k to be the number of clauses in If there is a 


satisfying assignment f o r 	p i c k one literal from each clause that is given the assignment true th e 
corresponding nodes in G form a stable set of size k If there is a stable set of size k then it must 
have exactly one node in each clique corresponding to a clause Furthermore	 the nodes in the stable 
set cannot correspond to both a literal and its negation	 so that we can form an assignment b y 
setting to true all literals selected in the stable set	 and extending this assignment to the remaining 
variables arbitrarily This is a satisfying assignment This is a characteristic reduction	 in that 
we build gadgets to represent the variables and clause structure within the framework of the new 
problem The NP completeness of two other problems follow immediately the clique problem 
given a graph G and a bound k decide if there is a clique in G of size k and the node cover 
problem given a graph G and a bound k decide if there exists a set of k nodes such that every edge 
is incident to a node in the set A somewhat more complicated reduction transforms SAT i n to the 
Hamiltonian circuit problem to show t h a t t o b e NP complete A seemingly slight generalization 
of bipartite graph matching	 the 
dimensional matching problem can be shown to be NP 
complete given disjoint node sets AB and C and a collection F of hyperedges of the form	 abc 
where a Ab B and cC does there exist a subset of F such that eachnode is contained in 
exactly one edge in the subset 

If we restrict the stable set problem to a particular constant v alue of k eg 	is G 
then this problem can be solved in P by e n umerating all possible sets of size In contrast to 
this	 Stockmeyer has shown that the colorability problem is NP complete	 by reducing SAT 
toit Let be a SAT form ula We construct agraph G from it in the following way First	 
construct a reference clique on three nodes	 called true false and undened these nodes will serve 
as a way of naming the colors in any coloring of the graph For each v ariable in construct a 
pair of adjacent nodes	 one representing the variable	 and one representing its negation	 and make 
them both adjacent to the undened node For each clause	 lll construct the subgraph shown 
in Figure below	 where the nodes labeled with literals	 as well as false F and undened U are 
the nodes already described It is easy to see that if has a satisfying assignment	 we c a n g e t a 
proper coloring of this graph as follows color the nodes corresponding literals that are true in the 
assignment with the same color as is given node true color analogously the nodes for false literals 
and then extend this coloring to the remaining nodes in a straightforward manner Furthermore	 
it involves only a little casechecking to see that if the graph is colorable	 then the colors can be 
interpreted as a satisfying assignment

 

l􀀀􀀀 
H􀀀 H H 
􀀀 
H􀀀 H H 
F􀀀 
l 􀀀 􀀀 􀀀 H 
H 
l 􀀀 􀀀 
H U􀀀 

Figure 
The integer programming problem de
ned as follows	 is N 
matrix A and an m vector b decide if there exists an integer n vethis case	 nding a reduction from SAT is trivial given a formula 
P 
ct
complete given an m 
or x such that Ax b 
represent each literal by 
n 
In 
a n 

integer variable bounded between and and for each B o o l e a n v ariable x constrain the sum of 


the variables corresponding to x and its negation to be at most The construction is completed 
by adding a constraint for each clause that forces the variables for the literals in the clause to sum 
to at least On the other hand	 to show that the problem is in NP requires more work	 involving 
a calculation that bounds the length of a smallest solution satisfying the constraints 􀀀if one exists 
at all 

The subset sum problem is also NP complete given a set of numb e r s S and a target numb e r 
t does there exist a subset of S that sums to t This is the 
rst problem that we h a ve encountered 
that is a number problem in the sense that it is not the combinatorial structure	 but rather the 
numbers that make this problem hard If the numbers are given in unary there is a polynomial 
time algorithm 􀀀such an algorithm is called pseudo
polynomial keep a 􀀀large	 but polynomially 
bounded table of all possible sums obtainable using a subset of the 
rst i numbers this is trivial 
to do for i and it is not hard to e
ciently nd the table for i given the table for i the table 
for in gives us the answer There are number problems that remain NP complete	 even if the 
numbers are encoded in unary such problems are called strongly NP 
complete One example 
is the 
partition problem g iv enaset S of the n integers that sum to nB does there exist a 
partition of S into n sets	 TT n where each Ti has elements that sum to B 

The complexity class NP nP 

If we are to believe the conjecture that P NP then there exists a nonempty complexity class 
N PnP One might ask the question is it true that every problem in NP is either NP complete or 
in P If P NP this question has a 􀀀trivial a
rmative a n s w er	 but a negative a n s w er to it 􀀀under 
the assumption the P NP might help explain the reluctance of certain problems to be placed 
in one of those two classes In fact	 Ladner has shown	 under the assumption that P NP that 
there is an extremely re
ned structure of equivalence between the two classes	 P and NP complete 

Theorem If L is decidable and L P then there exists a decidable language L such 
that L P LL but L L

pp 

Note that if L is NP complete	 the language L is in between the classes P and NP complete	 
if P NP and by repeatedly applying the result we see that there is a whole range of seemingly 
dierent complexity classes Under the assumption that P isdierent fro m NP 	do we know of 
any candidate problems that may lie in this purgatory of complexity classes The answer to this 
is maybe We will give four important problems that have not been shown to be either in P 
or NP complete The problem for which there has been the greatest speculation along these lines 
is the graph isomorphism problem given a pair of graphs G VE and G VE 
decide if there is a bijection VV such that ij E if and only if ij E Later in 
this section we will provide evidence that it is not NP complete	 and eortstoshow th a t it is in P 
have so far fallen short 􀀀see Chapter of this volume A problem that mathematicians since the 
ancient Greeks have been trying to solve is that of factoring integers a decision formulation that 
is polynomially equivalent to factoring is as follows given an integer N and a bound k does there 
exist a factor of N that is at most k A problem that is no harder than factoring is the discrete 
logarithm problem given a prime p a generator g and an natural numb e r xp 
nd l such 
that gl x mod p Finally there is the shortest vector problem where we are given a collection 
of integer vectors	 and we wish to nd the shortest vector in the Euclidean norm that can be 
represented as a nonzero integral combination of these vectors Here	 current evidence makes it 


seem likely that this problem is really NP complete related work is discussed elsewhere in this 
volume 􀀀see Chapter 

It is important to mention that there is an important subclass of NP which m a y also fall in this 
presumed gap Edmonds class of wellcharacterized problems	 NP co NP certainly contains P 
and is contained in NP F urthermore	 unless NP co NP it cannot contain any NP complete 
problem On the other hand	 the prevailing feeling is that showing a problem to be in this class is 
a giant s t e p t o wards showing that the problem is in P A result of Pratt shows that primality i s i n 
NP so it lies in NP co NP though as discussed above	 there is additional evidence that it lies 
in P The factoring problem	 which appears to be signi
cantly harder	 also lies in NP co NP 
since a prime factorization can be guessed along with certi
cate that each of the factors is indeed 
prime One interesting open question connected with NP co NP is concerned with the existence 
of a problem that is complete for this class One might hope that there is some natural problem 
that completely characterizes the relationship of NP co NP with P 􀀀in the same manner that 

SAT c haracterizes the P NP question 

One approach to shed light on the complexity of a problem that is not known to be either in 
P or NP complete	 has been to consider weaker forms of completeness for NP In fact	 Cooks 
notion of completeness	 though technically a weaker de
nition of intractability is no less damning 
L pL can be thought of as solving L by a restricted kind of subroutine call	 where 
rst some 
polynomialtime preprocessing is done	 and then the subroutine for L is called once Cook 
proposed a notion of reducibility w h e r e L is solved by using a polynomialtime Turing machine 
that can	 in one step	 get an answer to any query of the form	 is xL Note that any complete 
language L with respect to this reducibility still has the property t h a t L P if and only if P NP 
Karp focused attention on the notion p andwas abletoshow th a t NP completeness was 
p o werful enough to capture a wide range of combinatorial problems On the other hand	 it remains 
an open question to show that Cooks notion of reducibility is stronger than Karps is there a 
natural problem in NP that is complete with respect to Cook reducibility but not with respect 
to Karp reducibility Adleman Manders showed that nondeterminism and randomization can 
play a role in de
ning notions of reducibility and used these notions to show that certain numb e r 
theoretic problems were not	 for example	 in NP co NP unless NP co NP 

Oracles and relativized complexity classes 

In previous subsections	 we h a ve discussed techniques to provide evidence of the intractability 
of concrete problems in NP by p r o ving completeness results In this section	 we will be concerned 
with extensions of the model of computation where the analogue of the P versus NP problem can 
be resolved 

We h a ve mentioned earlier that oracles are used to compactly represent the input of some 
problems One can de
ne the analogue of the classes P and NP for problems whose inputs are 
oracles and it is easy to prove that these complexity classes are dierent For example	 if the oracle 
represents a set system on n elements	 then the problem to decide if this set system is nonempty i s 
clearly in NP but one has to ask 
n queries from the oracle to resolve it deterministically Similar 
results have also been proved for combinatorial problems that are naturally represented by oracles 
For example	 the matroid matching problem and the problem to decide if a matroid has girth at 
most k ie whether it has a cycle of length at most k are both clearly in NP but it has been 
shown that any deterministic algorithm solving them has to ask an exponential number of queries 


􀀀see Chapter 

Problems on graphs can also be given by a n o r a c l e Suppose that a graph eg 	on N 
n 
nodes is given by an oracle	 that can tell whether two nodes are adjacent The question is whether 
all reasonable decision problems on graphs require to ask some constant fraction of the queries 
This problem has a long history both for directed and undirected graphs	 and many attempts were 
made at giving su
ciently strong conditions before an accurate conjecture	 due to Aanderaa and 
Rosenb e r g w as proved by Rivest Vuillemin	 and later strengthened by Kahn	 Saks Sturtevant 
Consider a decision problem L where the instances are undirected graphs	 and L has three important 
properties nontriviality some graphs are in L but not all monotonicity )if G is an 
instance in L and G is formed by adding an edge	 then G is also in L invariance under 
isomorphism )if G is an instance in L and its nodes are relabelled to form G then G is also 
in L Then for any problem satisfying these two properties	 any correct procedure uses essentially 
N queries for some graph of order N In fact	 if N is a prime power	 Kahn	 Saks Sturtevant 
have shown that all NN queries must be asked 􀀀see Chapter These results are also 
relevant in comparing the adjacency matrix form of encoding graphs to the adjacency list encoding 

Another extension of the classes P and NP uses oracles as a source of computational power 
rather than as a source of information For a given language A we shall consider oracle Turing 
machines that	 during the computation	 may ask queries of the form is xA Here	 the oracle 
A is considered as part of the model of computation	 rather than as part of the input This notion 
of an oracle can help	 for example	 in understanding the relative di
culty of some problems 

For an language A 	w e denote by PA and NP 
A the relativized analogues of P and NP 
that are de
ned by T uring machines that use an oracle that decides membership in A In general	 
the relativized analogue of a complexity class C is denoted by CA The main result concerning 
oracle complexity classes	 due to Baker	 Gill Solovay is that the answer to the relativized 
version the P NP problem depends on the oracle The intuition for the 
rst alternative o f 
the following theorem is given by the case when the oracle is an input This is made rigorous 
by diagonalizing over all oracle Turing machines to construct an oracle A such that the language 

L A f 
n x A such that jxj ng is not in PA 
Theorem There exist languages A and B such that PA N P 
A c o N P 
A and PB 
N P 
B c o N P 
B 

Several of the theorems and proof techniques discussed in this survey easily extend to relativized 
complexity classes ie they relativize Asacorollarytotheabove theorem w ecanassertthat 
techniques that relativize cannot settle the P versus NP problem 

One might w onder which one of the two alternatives provided by the theorem of Baker	 Gill	 

Solovay i s m o r e t ypical We de
ne a random language A to be one that contains each w ord 
x independently with probability We s a y that a statement holds for a random oracle if 
the probability that the statement holds for a random language A in place of the oracle is The 
Kolmogorov law of probability theory states that if an event A is determined by the independent 
events	 BB and A is independent o f a n y e v ent that is a 
nite combination of the events Bi 
then the probability o f A is either or Applying this to the event A that PA NP 
A and the 

PAA

events Bi that the ith word is in the language A 	w e see that the probability o f NP for a 
random oracle A is either or Bennett Gill have provided the answers to these questions 


Theorem PA NP 
A and NP 
A co NP 
A for a random oracle A 

Evidence of intractability P SP A CE completeness 

In this subsection	 we turn to the question of the space complexity of problems When we 
discuss space complexity 	w e m a y assume that the Turing machine has only one work tape 􀀀and a 
separate input tape since by expanding the tape alphabet	 any n umber of tapes can be simulated 
by one tape without using more space We shall also assume that the Turing machine halts in a 
unique con
guration when accepting the input	 eg it erases its work tape	 moves both heads to 
the beginning of the tapes	 and enters a special accepting state 

We remarked when introducing P SP A CE that it was not an oversight t h a t N PSPACE was 
not de
ned	 since PSPACE N PSPACE This result is a special case of the following theorem 
of Savitch 

Theorem If Lis accepted by a nondeterministic Turing machine using space Sn log n 
then it is accepted by a deterministic Turing machine using space Sn 

Proof
 The proof is based on the idea of modeling the computation by a directed reachability 
problem and using a natural divideandconquer strategy I n a n y g i v en computation	 a nondeter 
ministic Turing machine M can be completely described by specifying the input head position	 
the contents of the work tape	 the work tape head position and the current state Consider the 
directed graph Gwhose nodes correspond to these con
gurations and whose arcs correspond to 
possible transitions of M The Turing machine accepts the input if and only if there is a path in 
Gfrom the starting con
guration to the 􀀀unique accepting con
guration 

Since Muses Sn space	 there are at most dSn con
gurations for some constant dand hence 
the length of a simple path in Gis at most dSn T o solve the reachability problem in G 	w e build 
a procedure that recursively calls itself to check for any nodes iand kof G and a bound l whether 
there is a path from ito kof length at most 
l There is such a path if there exists a midpoint o f 
the path j such that j can be reached from i 	and kcan be reached from jby paths of length at 
most 
l The existential quanti
er can be implemented by merely trying all possible nodes jin 
some speci
ed order The basis of this recursion is the case l where we merely need to know 
if ik 	or if i and k are connected by an arc of G and this can be easily checked in OSn 
spaceIn implementingthisprocedure	 weneed to keeptrack ofthecurrentmidpointateachlevel 
of the recursion	 and so we n e e d lS n space to do this To s i m ulate M by a deterministic Turing 
machine	 we run the procedure for the graph Gwith l Sn log dand the nodes corresponding to 
the starting and the accepting con
gurations 
􀀀 


A problem L is PSPA CE 
complete if L P SP A CE and for all L P SP A CE L pL 
The simplest P SP A CE complete problem is the problem of determining if two nodes are connected 
in a directed graph G 􀀀of order 
n th a t is g iv enby acircuitwith ninputs where the 
rst nspecify 
in binary a node iand the second nspecify a node j and the output of the circuit is if and only 
if ij is an arc of G This problem can easily be solved by a nondeterministic Turing machine 
using polynomial space	 hence it is in P SP A CE T o p r o ve that it is complete	 consider a language 
L PSPACE L can be reduced to this circuit
based directed reachability problem by 
introducing the graph Gused in the proof of Savitchs theorem It is easy to construct in polynomial 


time a polynomialsize circuit that decides if one con
guration follows another by one transition 
of M 

The idea of guessing a midpoint is also the main idea used to derive another P SP A CE 
complete problem The problem of the validity o f q u a n ti
ed Boolean formulae is as follows given 
a formula in rstorder logic in prenix form	 xx Qkxk xx k 
true decide ifitis valid 
This problem is clearly in P SP A CE The proof of its completeness is a mixture of Theorem 
and Theorem We use the alternation of existential and universal quanti
ers to capture the 
notion of the existence of a midpoint s u c h that both for all the 
rst and second halves of the 
computation are legitimate The basis of the recursion is now s o l v ed by building a Boolean formula 
to express that two con
gurations are either the same or one is the result of a single transition from 
the other 

An instance of the previous problem can be viewed as a game between an existential player 
and a universal player the existential player gets to choose values for x then the universal player 
chooses for x and so on The decision question amounts to whether the 
rst player has a strategy 
so that must evaluate to true There are many other P SP A CE complete problems known	 and 
most of these have a gamelike a vor An example of a more natural P SP A CE complete game is 
the directed Shannon switching game g iv enagraph G withtwo nodes s and t 	t wo players 
alternately color the edges of G where the 
rst player	 coloring with red	 tries to construct a red 
path from s to t whereas the second player	 coloring with blue	 tries to construct a blue st cut 
does the rst player have a winning strategy for G Note that this result is in stark contrast to the 
undirected case	 which can be solved in polynomial time 􀀀see Chapter 

The role of games in P SP A CE completeness suggests a new ty p e o f T uring machine	 called an 
alternating Turing machine which w as originally proposed by Chandra	 Kozen Stockmeyer 

Consider a computation to be a sequence of moves made by t wo players	 an existential player 
and a universal player The current state indicates whose move it is	 and in each con
guration the 
speci
ed player has several moves from which t o c hoose Each computation path either accepts or 
rejects the input The input is accepted if the existential player has a winning strategy that is	 if 
there is a choice of moves for the existential player	 so that for any c hoice of moves by the universal 
player	 the input is accepted For simplicity assume again that each computation path has the 
same numb e r o f m o ves As before	 the time to accept an input x isthisnumb e r o f m o ves	 and the 
space needed to accept x is the maximum space used on any computation path Observe that a 
nondeterministic machine is an alternating machine where only the existential player moves 

The role of P SP A CE in the de
nition of these machines suggests that alternating polynomial 
time is closely related to P SP A CE and indeed this is just a special case of a general phenomenon 
Let ATIME T n and ASPACE S n denote the classes accepted by an alternating Turing 
machine with OT n time and OSn space	 respectively Chandra	 Kozen Stockmeyer proved 
two fundamental results characterizing the relationship of alternating classes to deterministic and 
nondeterministic ones Note that the 
rst result	 in essence	 implies Savitchs theorem	 and in fact	 
the proof of the last inclusion of Theorem is very similar to the proof of Savitchs theorem 

Theorem If Tn n th en 

ATIME Tn DSPACE Tn NSPACE Tn ATIME Tn 


nS

Theorem If Sn log n then ASPACE S n DTIME c 

Among the consequences of these results	 we see that AP PSPACE One can view an alternating 
Turing machine as extremely idealized parallel computer	 since it can branch o a n u n bounded 
number of parallel processes that can be used in determining the 
nal outcome Therefore	 one 
can consider these results as a proven instance of the parallel computation thesis parallel time 
equals sequential space up to a polynomial function 

The polynomialtime hierarchy 

The de
nition of P SP A CE using alternating Turing machines suggests a hierarchy o f c o m 
plexity classes between NP and P SP A CE called the polynomial
time hierarchy The kth 
level of the polynomialtime hierarchy can be de
ned in terms of polynomialtime alternating Tur 
ing machines where the number of alternations between existential and universal quanti
ers 

is less than k Equivalently 	w e can de
ne

P 
k

fLj L P 
is if k is odd	 

such that xL if and only if 

Qkyk 

L g

e also de
ne 
where Qk and if k is even Note that

py py 

xyy y

kpp 

P

P and

PP 
k

to be co

P 
k 

P 
k 

P 
k 
P 
k

NP W 

Clearly The following 

P

generalized coloring problem gives a natural example of a problem in G i v en input graphs 

G and H 	c a n w e color the nodes of G with two colors so that the graph induced by e a c h color does 
not contain H as a subgraph 

Alternatively it is possible to de
ne the polynomialtime hierarchy in terms of oracles	 as was 
done in the original formulation by Meyer Stockmeyer For complexity classes C and D 

let CD

ACdenotetheunion of 

over all A D Consider again the generalized coloring problem 

it is not hard to see that there is nondeterministic polynomialtime Turing machine to solve it	 
given an oracle for the following problem A g iv en G and H decide if H is a subgraph of G Since 

 NP 	w e see that this coloring problem is in NP

PN

In fact	

P

NP

PN

and in general	

A 

k

NP 
P Unfortunately for each new complexity class	 there is yet another host of unsettled 

P 
k 

questions 

P 
k 

P 
k

F or each k is

P 
k 

P 
k

Open Problems For each k is 

Contained in these	 for k are the P NP and NP co NP questions	 and as was true for 
those questions	 one might hope to nd complete problems on which to focus attention in resolving 
these open problems We de
ne these notions of completeness with respect to polynomialtime 

reducibility so that L is complete for C if and only if L C and all problems in C reduce

p

to 

L As might be expected	 analogues of the satis
ability problem which allow a particular numb e r 
of alternations in the formulae can be used to provide a complete problem for each level of the 
hierarchy On the other hand	 it is more satisfying to have more natural complete problems	 and 

P

Rutenb e r g s h o wed that the generalized coloring problem is	 in fact	 complete for Another 

problem of identical complexity is a similarly avored node deletion problem given graphs G and 
H and an integer k decide if there is a subset of k nodes that can be deleted from G 	so that the 
remaining graph no longer has H as a subgraph 

One piece of good news concerning this in
nite supply of open problems	 is that their answers 

may be related There is a principle of upward inheritability t h a t s a ys that if

P 
l 

P 
l

for some 

level l then equality holds for all levels kl In fact	 

P 
l 

P 
l

implies that the entire hierarchy 

collapses to that level 

ie

P 
l 

P 
k

for all kl Note that P NP if and only if P PH 


P

where PH kk 

As we shall see	 the polynomialtime hierarchy has helped to provide insight i n to the structure 
of several complexity classes Perhaps the 
rst result along these lines is due to Sipser	 who used a 
beautiful hashing function technique to show that BPP is in the polynomialtime hierarchy and 
in fact	 can be placed within 
PP 

Furst	 Saxe Sipser discovered an interesting connection between constantdepth circuit 
lower bounds and separating relativized complexity classes In particular	 they showed that there 
are important consequences of an exponential lower bound on the size of a constantdepth circuit 
for the parity function the sum modulo of the bits of the input Based on earlier results of 
Furst	 Saxe Sipser and Ajtai	 Yao proved a su
ciently strong lower bound to yield the 
following theorem 

Theorem There exists an oracle A that separates the polynomialtime hierarchy f r o m 

P AA

P SP A CE that is P SP A CE

k k 

The idea of the proof is as follows First one shows that it is su
cient to consider alternating 
Turing machines in which e v ery branch of the computation has a single oracle question at the 
end of the branch The computation tree of such an alternating Turing machine with k levels of 
alternation corresponds to a depth k circuit where the oracle answers are the inputs For any oracle 
A 	w e de
ne the language LA f 
njA contains an odd number of strings of length ng LA 
is in P SP A CE 
A for any oracle A Using diagonalization and the result that for any constant c 	a 

logc 
n

constantdepth circuit that computes the parity function has n gates	 one can construct an 

P A

oracle A such that LA is not in 

k k 

Another related problem is to separate the 
nite levels of the polynomialtime hierarchy u s i n g 

P A P A

oracles Baker Selman proved the existence of an oracle A such that 􀀀and conse 

P A P A

quently Sipser showed that an oracle that separates 
nite levels of the polynomial 
time hierarchy can be obtained via a connection to lower bounds on the size of constantdepth 
circuits	 similar to the one used in Theorem The following theorem is based on this as well 
as the requisite lower bounds for a certain function Fk which is in some sense the generic function 
that is computable in depth k these lower bounds were obtained through a series of results by 
Sipser	 Yao and Hastad 

P Ak 
P Ak

Theorem For every k there exists an oracle Ak such that kk 

Techniques for proving the circuit complexity l o wer bounds used in Theorems and 
are discussed in Chapters and Based on stronger circuit complexity results	 Babai and Cai 
separated P SP A CE from the 
nite levels of the hierarchy b y random oracles The question whether 
random oracles separate the 
nite levels of the polynomialtime hierarchy remains open Another 
open question concerning random oracles is whether PA NP 
A co NP 
A for a random oracle 
A 

Evidence of intractability #P completeness 

Consider the counting problem of computing the number of perfect matchings in a bipartite 
graph If this is cast as a decision problem	 it does not appear to be in NP since it seems 


that the number of solutions can only be certi
ed by writing down possibly exponentially many 
matchings However	 consider modifying the de
nition of NP to focus on the number of good 
certi
cates	 rather than the existence of one let P be the class of problems for which there exists 
a language L P and a polynomial pn s u c h that for any input x the only acceptable output 
is z jfy jyj p jxj and xy L gj Clearly the problem of counting perfect matchings in 
a bipartite graph is in P Any problem in P can be computed using polynomial space	 since 
all possible certi
cates y may be tried in succession A recent result of To d a g i v es evidence of the 
intractability of this class by s h o wing that PH P 
P 

We can also de
ne a notion of a complete problem for P To do this	 we use a reduction 
analogous to that used by Cook Let P and P be counting problems	 where the output for input 
x is denoted by Px and Px respectively The problem P reduces to P if there exists a 
polynomialtime Turing machine that can compute P if it has access to an oracle that	 given x can 
compute Px in one step We de
ne a counting problem to be P 
complete ifitis in P and 
all problems in P reduce to it A stronger notion of reducibility analogous to the notion used 
by Karp	 is called parsimonious an instance x of P is mapped in polynomial time to fx fo r 
P 	such that Px Pfx For either notion of reducibility 	w e see that any polynomialtime 
algorithm for P yields a polynomialtime algorithm for P It is not hard to see that the proof of 
Cooks theorem shows that the problem of computing the number of satisfying assignments of a 
Boolean formula in conjunctive normal form is P complete Furthermore	 by being only slightly 
more careful	 it is easy to give parsimonious modi
cations of the reductions to the clique problem	 
the Hamiltonian circuit problem	 and seemingly any NP complete problem	 and so the counting 
versions of NP complete problems can be shown to be P complete 

Surprisingly not all P complete counting problems need be associated with an NP complete 
problem Computing the number the perfect matchings in a bipartite graph	 􀀀or equivalently 
computing the permanent of a matrix is a counting version of a problem in P the perfect 
matching problem	 and yet Valiant has shown that this problem is P complete This made 
it possible to prove t h a t a v ariety o f c o u n ting problems are P complete although they are based 
on polynomially solvable decision problems 

There are many problems that are essentially P complete	 although they do not have t h e 
appearance of a counting problem An important example is the problem of computing the volume 
of a convex body In the special case when the body is a polytope given by a system of linear 
inequalities	 Khachiyan and Dyer Frieze independently proved that this is P hard For some 
problems	 computing a good estimate su
ces	 and this might b e m uch easier If the convex body is 
given by an oracle that answers whether a given point is feasible	 and if not produces a separating 
hyperplane 􀀀see Chapter then it is most natural to only estimate the volume However	 B!ar!any 

F uredi	 extending work of Elekes	 proved that if U and L are upper and lower bounds on the 
volume of a d dimensional convex body that are computed by an algorithm that makes only a poly 
nomial number of calls to the oracle	 then U L d log d 
d Surprisingly randomization can 
overcome this intractability D y er	 Frieze Kannan showed that there is a randomized algorithm 

that	 given any computes upper and lower bounds U and L such that U L uses a 
number of calls to the oracle that is bounded by p o l y n o m i a l i n d and log and is correct 
with probability at least 

Another problem that has been shown to be intimately connected with the estimation of the 
value of counting problems is that of uniformly generating combinatorial structures As an example	 


suppose that a randomized algorithm requires a perfect matching in a bipartite graph G to be 
chosen uniformly from the set of all perfect matchings in G h o w can this be done Jerrum	 Valiant 

V azirani have s h o wn that a relaxed version of this problem	 choosing perfect matchings that 
are selected with probability within an arbitrarily small constant factor of the uniform value	 is 
equivalent to the problem of estimating the number of perfect matchings using a randomized 
algorithm In fact	 their result carries through to most counting(generation problems related 
to problems in NP since it requires only a natural selfreducibility property that says that an 
instance can be solved by handling some number of smaller instances of the same problem 

Stockmeyer has provided insight i n to estimating the value of P problems	 by trying to place 
these problems within the polynomialtime hierarchy Using Sipsers hashing function technique	 
Stockmeyer showed that for any problem in P andany
 xed valueof d there exists a 
polynomialtime Turing machine with a 
P complete oracle that computes a value that is within 

d

a factor of􀀀 n of the correct answer 

P r o o f o f in tractability 

It is	 of course	 far preferable to prove that a problem is intractable	 rather than merely giving 
evidence that supports this belief Perhaps the 
rst natural question is	 are there any decidable 
languages that require more time than Tn The diagonalization techniques used to show that 
there are undecidable languages can be used to show that for any T uring computable Tn there 
must exist such a language consider the language L of all i such that if i is run on the Turing 
machine Mi that i encodes	 either it is rejected	 or it runs for more than Tn steps It is easy to 
see that L is decidable	 and yet no Turing machine that always halts within Tn steps can accept 
L Using our stronger assumption about Tn full timeconstructibility we are able to de
ne 
such a language that is not only decidable	 but can be recognized within only slightly more time 
than Tn The additional logarithmic factor needed in Theorem which c o m bines results 
of Hartmanis Stearns and Hennie Stearns	 is due to the fact that the fastest known 
simulation of a multitape Turing machine by a m a c hine with some constant n umber of tapes slows 
down the machine by a logarithmic factor 

Tn lo g Tn 

Theorem If lim inf then there exists L DTIM E T nDTIME T 

n Tn 

Since any m ultitape machine can be simulated by a tape machine without using any additional 
space	 the corresponding space hierarchy theorem of Hartmanis	 Lewis Stearns does not require 
the logarithmic factor Seiferas	 Fischer Meyer have p r o ved an analogous	 but much more di
cult	 
hierarchy theorem for nondeterministic time 

Tn 

Theorem If lim inf then there exists L NTIM E T n NTIME T 

n Tn 

Although the proofs of these theorems are nonconstructive	 Meyer Stockmeyer developed 
the following strategy that makes use of completeness results in order to prove l o wer bounds on 
particular problems Intuitively a completeness result says that a problem is a hardest problem 
for some complexity class	 and Theorems and can be used to show that certain 
complexity classes have p r o vably hard problems Consequently these two pieces imply that the 
complete problem is provably hard 


As an example	 consider the circuit
based large clique problem Lcc which is the problem 
analogous to the circuitbased directed reachability problem	 that tests whether the compactly 
represented input graph on N 
n nodes has a clique of size N This problem is complete for 

k 


the class N EXPTIM E k N TIM E 
n with respect to polynomialtime reducibility This 
c a n b e s e e n b y i n troducing the circuitbased version of satis
ability a formula is represented by a 
polynomialsize circuit that outputs for input ij when literal li is in the jth clause	 where i 
and j are given in binary The generic reduction of Cooks theorem translates exactly to show that 
circuitbased satis
ability i s N EXPTIM E complete	 and the completeness of Lcc follows by u sin g 
essentially the same reduction used to show t h e NP completeness of the ordinary clique problem 

􀀀 


Now consider a language L NTIM E 
n N TIM E 
n speci
ed by Theorem Since 
n pn is

L pLcc 	th en Lcc N TIM E 
c 
implies that L NTIM E pn 
c 
where pn nk 
the time bound for the reduction By choosing c k 	w e obtain the following theorem 

Theorem There exists a constant c such that Lcc N TIM E 
nc 


One interpretation of this result is that there exist graphs speci
ed by circuits such that proofs 
that these graphs have a large clique require an exponential number of steps in terms of the size 
of the circuit Observe that we w ould have been able to prove a stronger result if we w ould have 
had a better bound on the length of the string produced by the reduction Lower bounds proved 
using this strategy are often based on completeness with respect to reducibilities that are further 
restricted to produce an output of length bounded by a linear function of the input length 

This strategy has been applied primarily to problems from logic and formal language theory A 
result of Fischer Rabin that contrasts nicely with Theorem concerns Lpa the language 
of all provable sentences in the theory of arithmetic for natural numbers without multiplication	 
which w as shown to be decidable by Presburger 

cn 


Theorem There is a constant c such that Lpa N TIM E 

A representative sample of problems treated in this fashion is surveyed by Stockmeyer 

There are two other important results that separate complexity classes Hopcroft	 Paul and 
Valiant showed that DTIM E Tn DSPACE Tn log Tn and thus time is not the 
same complexity measure as space Paul	 Pippenger	 Szemeredi and Trotter showed that 
DTIMEn NTIMEn 

Extensions of NP short proofs via randomization 

In the same way that randomized algorithms give rise to an extended notion of e
ciently 
computable	 randomized proofs give rise to an extension of NP the class of languages for which 
membership is e
ciently provable Randomized proofs give o verwhelming statistical evidence 
In creating this branch of complexity theory Babai and Goldwasser	 Micali Racko 

have g i v en de
nitions to capture related notions of proof based on statistical evidence The 
interested reader is directed to the surveys by Goldwasser and Johnson 

Suppose that King Arthur has two graphs G and G and his magician Merlin wants to convince 
him that the two graphs are not isomorphic The graph isomorphism problem is not known to be 


in co NP but Goldreich	 Micali Wigderson have given the following way for Merlin to convince 
Arthur that the two graphs are not isomorphic Merlin asks Arthur to choose one of the two graphs	 
randomly relabel the nodes	 and show him this random isomorphic copy of the chosen graph Merlin 
will tell which graph Arthur chose If the two graphs are isomorphic	 then Merlin has only a fty 
percent c hance of choosing the right graph	 assuming that he cannot read Arthurs mind If Merlin 
can successfully repeat this test several times	 then Arthur can fairly safely conclude that Merlin can 
distinguish isomorphic copies of the two graphs in particular	 the two graphs are not isomorphic 

The above randomized proof is a prime example of the interactive proof de
ned by Goldwasser	 
Micali Racko An interactive protocol consists of two T uring machines the Prover 􀀀Mer 
lin that has unrestricted power and the Veri
er Arthur that is restricted to be a randomized 
polynomialtime Turing machine The two m a c hines operate in turns	 and communicate only be 
tween turns via a special tape The Prover is trying to convince the Veri
er that a common input 
x is in a language L A language L has an interactive proof system if there exists an interactive 
protocol such that if xL then the Veri
er accepts with probability at least if xL then 
for any T uring machine used in place of the Prover	 the Veri
er rejects with probability at least 

Let IP denote the class of languages that have a n i n teractive proof system with a polynomial 
number of turns Note that	 once again	 the choice of probability is arbitrary 

Babai has proposed a similar	 but seemingly weaker	 version of a randomized proof system	 an 
Arthur Merlin game in trying to capture a complexity class just above NP It can be de
ned 
in the same way a s a n i n teractive proof system with the assumption that each machine may access 
the others work and randomizing tapes Note the importance of privacy in the above i n teractive 
protocol Goldwasser Sipser proved	 however	 that interactive proofs and Arthur)Merlin games 
de
ne the same complexity class 

One can de
ne randomized proof hierarchies in a way analogous to the polynomialtime hier 
archy W e consider the class of languages accepted by a n i n teractive proof system 􀀀or an Arthur) 
Merlin game with less than k alternations of turns Babai introduced AM to denote the class 
of languages that have a n A r t h ur)Merlin game where a single move of Arthur is followed by a 
single move of Merlin It would be natural to conjecture that these hierarchies are strict However	 
Babai proved that if a problem has an Arthur)Merlin game with a nite number of turns than it is 
in AM Since the equivalence between interactive p r o o f s a n d A r t h ur)Merlin games increases the 
number of turns only by a constant	 the same is true for interactive proofs with a 
nite numb e r o f 
turns 

On the other hand	 it appears that IP which a l l o ws a polynomially bounded numb e r o f a l 
ternations	 is a signi
cantly richer class than AM Lund	 Fortnow	 Karlo Nisan showed that 
PH IP and Shamir extended their techniques to prove the following theorem 

Theorem IP PSPACE 

One way to view this result is that it is possible to convince someone of a theorem in polynomial 
time	 if it can be proven using a polynomialsized blackboard An interesting aspect of these results 
is that they do not relativize	 since	 for example	 Fortnow Sipser have constructed an oracle A 

AA

for which co NP is not contained in IP There is evidence that AM is a more restrictive 
class Just as BPP P poly one canshow that AM is contained in NP poly a nonuniform 

P PP

extension of NP Babai has shown that AM by extending the proof that BPP 


It appears that AM does not contain co NP but to prove this would imply that NP co NP 
Nonetheless	 the following theorem	 due to Boppana	 Hastad Zachos	 provides some evidence 

PP

Theorem If co NP AM then AM 

We h a ve seen that the graph nonisomorphism problem is in AM Therefore	 Theorem 
implies that if the graph isomorphism problem is NP complete	 then 
PP AM 

Goldwasser	 Micali Racko introduced the interactive proof system in order to characterize 
the minimum amount o f k n o wledge that needs to be transferred in a proof Interactive proofs 
make it possible to prove	 for example	 that two graphs are isomorphic	 without giving any further 
clue about the isomorphism between them These aspects of interactive proofs shall be discussed 
in Chapter 

Note added in galleys In the years since this survey was written there have b e e n q u i t e a n umb e r 
of very signi cant developments beyond the results mentioned here We h a ve already mentioned 
the result that IP PSPACE this result was proved just in time to be included in the nal 
revised version sent to the publisher but it has turned out that this was more a beginning than 
a conclusion BenOr Goldwasser Kilian Wigderson introduced an analogous notion of mul 
tiprover interactive proofs in which t h e V eri er can be convinced by s e v eral independent Provers 
that cannot communicate with each other during the protocol Fortnow Rompel Sipser gave 
an alternate characterization of this class MIP w h i c h w as used by Babai Fortnow Lund to 
prove that MIP N EXPTIM E Fiege Goldwasser Lov	asz Safra Szegedy showed using 
ideas from the proof that MIP N EXPTIM E that there is a fundamental connection between 
randomized complexity classes and proving that certain optimization problems are hard to solve 
even approximately Extensions of this result by Arora Safra and Arora Lund Motwani Sudan 

Szegedy led to the ultimate result along these lines NP is exactly the class of languages L for 
which there is the following type of probabilistically checkable proof for any input x the Veri eris 
given a certi cate of polynomial length of which i t m a y q u e r y O bits based on O 􀀀log jxj random 
coin 
ips for each xL there exists a certi cate such that the Veri er always accepts for each 
xL given any certi cate the Veri er rejects with probability at least For a survey of these 
results the reader is referred to Johnson 

Living with Intractability 

The knowledge that a problem is NP complete is little consolation for the algorithm designer 
who needs to solve it Contrary to their theoretical equivalence	 all NP complete problems are not 
equally hard from a practical perspective In this section	 we will examine two approaches to these 
intractable problems that	 while not overcoming their inherent di
culty 	m a k e them appear more 
manageable In this process	 
ner theoretical distinctions will appear among these problems that 
help to explain the empirical evidence 

The complexity of approximate solutions 

Most of the NP complete problems in Karps original paper are decision versions of opti 
mization problems this is also true for a great majority of the problems catalogued by Garey 
Johnson Although the combinatorial nature of these problems makes it natural to focus on 


optimal solutions	 for most practical settings in which these problems arise it is nearly as satisfying 
to obtain solutions that are guaranteed to be nearly optimal In this subsection we will briey 
survey the sorts of performance guarantees that can and cannot be obtained for particular 
combinatorial problems For further discussion of the algorithmic techniques used in obtaining 
nearoptimal solutions	 the reader is referred to Chapter Throughout this section	 OPT I 
will denote the optimal value of an instance I of a particular combinatorial optimization problem 

It is possible that deciding if OPTI k is NP complete	and yeta solution ofvaluenomore 
than OPT I can be computed in polynomial time In fact	 this is true for the edge coloring 
problem where we are given an undirected simple graph G and an integer k and we wish to color 
the edges with as few colors as possible so that no two edges incident to the same node receive t h e 
same color Holyer showed that it is NP complete to decide if a cubic graph can be edgecolored 
On the other hand	 Vizing proved that the minimum number of colors needed is at most one more 
than maximum degree of G and his proof immediately yields a polynomialtime algorithm that 
uses at most OPT I colors Since edgecoloring graphs with chromatic index is trivial	 this 
also yields an algorithm that always uses no more than OPT I a polynomialtime algorithm 
with such a n absolute performance guarantee is often called a (approximation algorithm 
On the other hand	 it is easy to see that this is the best possible performance guarantee	 unless 
P NP Suppose that there exists a approximation algorithm for edge coloring with 
If this algorithm is run on a cubic graph that can be colored with three colors	 then the algorithm 
must return a coloring that uses fewer than four colors it returns an optimal coloring 

One type of strong approximation result is called a fully polynomial approximation scheme 
this is a family of algorithms fA g where A is a approximation algorithm and the depen 
dence of the running time on is bounded by a polynomial in By solving rounded instances 
with only a limited number of signi
cant digits	 Ibarra Kim gave s u c h a s c heme for the knapsack 
problem given n pieces to be packed into a knapsack of size B where piece j has size sj and value 
vj 	p a c k a subset of pieces of total size B with maximum total value Note that it is impossible 
to improve the dependence of the running time on to a polynomial in log since it is always 
possible to choose of polynomial length	 such t h a t AI OPTI and thus by i n tegrality 
AI OPTI The same argument implies an important result of Garey Johnson if a prob 
lem is strongly NP complete	 then there is no fully polynomial approximation scheme for it unless 
P NP If the running time of A may depend arbitrarily on it sometimes possible to obtain 
such a polynomial approximation scheme for strongly NP complete problems Hochbaum 
Shmoys showed that this is the case for the following machine scheduling problem each of 
n jobs is to be scheduled on one of m machines	 where job j takes time pj onany m achine	 and 
the aim is to minimize the time by w h i c h all jobs are completed In fact	 the idea of studying 
the performance guarantees of heuristics for optimization problems was 
rst proposed by Graham 

in the context of this problem	 who gave a approximation algorithm 

It is sometimes too restrictive to focus on approximation algorithms A good illustration of 
this is the bin
packing problem g i v en a collection of n pieces	 where piece j has size sj 	h ow 
many bins of size B are needed to pack all of the pieces Since it is easy to formulate the subset 
sum problem as a question of whether bins su
ce	 we see that a approximation algorithm with 
w ould imply that P NP H o wever	 Johnson showed that a simple heuristic uses at most 
OPT I bins This suggests that an asymptotic performance guarantee may also 
b e i n teresting	 where we consider the in
mum of the absolute performance guarantee for instances 


with OPTI k 􀀀as k It was a great surprise when Fernandez de la Vega Lueker not 
only substantially improved this bound	 but gave a polynomial approximation scheme with 
respect to asymptotic guarantees Perhaps even more surprisingly Karmarkar Karp extended 
this to give s u c h a s c heme where the dependence of the running time on was bounded by a 
polynomial 

If it is possible to scale up the data to generate an equivalent problem	 such as using processing 
times Mpj in the machine scheduling problem	 any distinction between the absolute and asymp 
totic performance guarantees disappears For node coloring	 the following graph composition 
accomplishes this scaling take M copies of the graph	 and make e a c h pair of nodes in dierent 
copies adjacent The NP completeness of colorability again implies that an absolute performance 
guarantee better than is unlikely In fact	 Garey Johnson use a more intricate compo 
sition technique to increase this ratio	 and thereby prove that an asymptotic performance guarantee 
less than would imply that P NP 

For some problems	 such a s t h e traveling salesman problem Gonzalez Sahni observed 
that no constant performance guarantee is possible unless P NP In this example	 where the 
aim is nd a minimum length Hamiltonian circuit in a complete graph where edge e has length ce 
one can use a approximation algorithm to decide the Hamiltonian circuit problem for a graph 
G VE set ce fo r eE and jV j otherwise However	 Christo
des has given a 

(approximation algorithm for instances that satisfy the triangle inequality 

For the great majority of problems	 such as node coloring	 there is both no constant performance 
guarantee	 nor any evidence that such an algorithm does not exist In the case of the maximum 
stable set problem	 for which the best known algorithm has performance guarantee little better 
than On log n there is some evidence that no polynomial approximation scheme exists Garey 

Johnson have given another graph composition technique to show that if performance guarantee 

is obtained	 then this can be used to obtain a approximation algorithm By repeatedly apply 
i n g t h i s t e c hnique	 it is possible to convert any approximation algorithm	 where is a constant	 
into a polynomial approximation scheme There are few other techniques that provide evidence 
for the intractability of computing nearoptimal solutions Recently 	P apadimitriou Yannakakis 
have proposed a complexity class	 along with a notion of completeness	 that attempts to charac 
terize those problems that have a constant performance guarantee	 but do not have a polynomial 
approximation scheme 

Note added in galleys In the years since this survey was written there have been dramatic advances 
in proving that certain problems are also hard to approximate Feige Goldwasser Lov	asz Safra 

log log n

Szegedy showed that unless NP DTIME n there does exist a approximation algorithm 
for maximum stable set problem for any constant Arora Safra strengthened this to show 
that achieving such an approximation is NP hard and this was strengthed even further by A r o r a 
Lund Motwani Sudan Szegedy who proved that there exists an such that there does 
not exist an n approximation algorithm unless P NP These techniques have yielded sign cant 
results for other problems as well Lund Yannakakis proved that any absolute performance 
guarantee that can be obtained for the minimum node coloring problem can also be obtained 
for the maximum stable set problem Arora Lund Motwani Sudan Szegedy also showed that 
unless P NP there does not exist a polynomial approximation scheme for any complete problem 
in the class MAX SNP proposed by P apadimitriou Yannakakis For example a corollary of this 
result is that there does not exist a polynomial approximation scheme for the traveling salesman 


problem with the triangle inequality unless P NP F or a survey of this research the reader is 
referred to Johnson 

Probabilistic analysis of algorithms 

One justi
ed criticism of complexity theory is that it focuses on worstcase possibilities	 and 
this may in fact be unrepresentative of practical reality In this section	 we will briey indicate 
some of the results that are concerned with the probabilistic analysis of algorithms	 where inputs 
are selected according to a speci
ed probability distribution	 and the average behavior is studied 
Many related results are presented in Chapter and the reader is referred there	 as we l l a s t o t h e 
surveys of Karp	 Lenstra	 McDiarmid Rinnooy Kan and Coman	 Lueker Rinnooy K a n 

We shall also sketch the main ideas of an analogue of NP completeness	 recently proposed 
by Levin to provide evidence that a problem is hard to solve i n e v en a probabilistic sense 

For all of the problems mentioned in the subsection on the worstcase analysis of heuristics	 it is 
possible to obtain much more optimistic results for the averagecase analysis under the assumption 
that the input is drawn from a speci
ed probability distribution Unfortunately these results are 
rely heavily on the particular distribution selected	 and an approach t o t h e a veragecase analysis 
of algorithms that is insensitive to this	 would be an important a d v ance As an example	 for the 
traveling salesman problem with edge lengths that are independently and identically distributed 

􀀀iid uniformly over the interval Karp has given a heuristic where the expected value of 
its relative error is On On the other hand	 the nodes may be selected iid uniformly 
in the unit square and the length of edge is given by the Euclidean distance between its 
endpoints In this case	 Karp has given a dierent algorithm that has the stronger property 
that the relative error converges to almost surely as n This result	 which stimulated much 
work in the area of probabilistic analysis	 is based in part on a result of Beardwood	 Halton 
Hammersley which p r o ves that	 for instances selected as above	 there exists a constant c such that 

p

OPTI nc almost surely 

Similar results are also known for such problems as node coloring and the Hamiltonian circuit 
problem This work grew out of the theory of random graphs of Erdos and Renyi	 which is treated in 
Chapter A common way t o c hoose a random graph is to include each possible edge independently 
with probability For the rst problem	 it is possible to prove that a simple greedy method is	 
in probability a factor of two more than optimal For the latter	 it is possible to give an algorithm 
that always gives a correct answer and runs in expected polynomial time 

Although the probabilistic analysis of algorithms has focused mainly on NP complete problems	 
it has often served as a useful tool to show that the averagecase running time of certain algorithms 
is much better than the worstcase running time The most important example of this is the simplex 
method for linear programming	 which is a practically e
cient algorithm that was shown to have 
exponential worstcase running time by Klee Minty B o r g w ardt and Smale	 independently showed 
that variants of the simplex method take polynomial expected time under certain probabilistic 
assumptions For a thorough survey of results in this area	 the reader is referred to Shamir 

Not all problems in NP have been solved e
ciently even with probabilistic assumptions	 and 
only the simplest sorts of distributions have been analyzed This raises the specter of intractability 
are there distributions for which certain NP complete problems remain hard to solve Levin 
has proposed a notion of completeness in a probabilistic setting Once again	 evidence for hardness 
is given by s h o wing that if a particular problem in NP with a speci
ed input distribution can 



be solved in expected polynomial time	 then every such problem and distribution pair can also be 
solved so e
ciently F or a more complete discussion	 the reader is encouraged to read the column 
of Johnson One of the motivations for studying such truly intractable problems come from 
the area of cryptography which attempts to use the intractability of a problem to the algorithm 
designers advantage see Chapter 

A bit of care must be given in formulating the precise notion of polynomial expected time	 so 
that it is insensitive to both the particular choice of machine and encoding If x denotes the 
probability that a randomly selected instance of size n is x and Tx is the running time on x then 
one would typically de
ne expected polynomial time to require that the sum of xT x o ver all 
instances of size n is Onk for some constant k Instead	 we consider to be the density function 
over the set of all instances I and require that P xT x 
k jxj for some constant k

xI 

P

Levins notion of random NP requires that the distribution function Mx 
xi 
i can be 
computed in P where each instance is viewed as a natural number This notion does not seem to 
be too restrictive	 and includes all of the probability distributions discussed here It remains only 
to de
ne the notion of reducibility As usual	 yes instances must be mapped by a polynomial 
time function f to yes instances	 and analogously for no instances	 but one must consider the 
density functions as well The pair L reduces to L if in addition we require that x 
is at least a polynomial fraction of the total probability of elements that are mapped to x by f 

Levin showed that all of random NP reduces to a certain random tiling problem Instances 
consist of integers kN 	asetoftiletypes	 each ofwhichis aunitsquarelabeled withlettersin 
its four corners	 and a sidebyside sequence of k such tiles where consecutive tiles have m a t c hing 
labels in both adjoining corners We wish to decide if there is a way of extending the sequence to 
ll 
out an NN square	 where adjacent tiles have m a t c hing labels in their corresponding corners	 and 
the top row starts with the speci
ed sequence of tiles The instances are selected by 
rst randomly 
choosing a value for N where N is set equal to n with probability proportional to nn 
k is chosen uniformly between and N the tile types are chosen uniformly and then the tiles in 
the sequence are selected in order uniformly among all possible extensions of the current sequence 
More recently 	V enkatesan Levin have shown that a generalization of the problem of edge coloring 
digraphs where for certain subgraphs	 the number of edges given each color is speci
ed is also 
random NP complete 

Inside P 

In this section we shall focus on the complexity of problems in P After proving that a problem is 
in P the most important next step undoubtedly is to 
nd an algorithm that is truly e
cient	 and 
not merely e
cient in this theoretical sense However	 we will not address that issue	 since that 
is best deferred to the individual chapters that discuss polynomialtime algorithms for particular 
problems In this section	 we shall address questions that relate to machineindependent complexity 
classes inside P 

From a practical viewpoint	 the most appealing complexity class inside P is the class of languages 
for which some polynomialtime algorithms can be speeded up signi
cantly if several processors 
work simultaneously We shall discuss parallel computation	 and focus on the complexity class 
NC which serves as a theoretical model of e
cient parallel computability 	m uch a s P serves as a 
theoretical model of e
cient sequential computation 


We shall also consider the space complexity of problems in P Recall that the parallel compu 
tation thesis suggests that there is a close relationship between sequential space complexity and 
parallel time complexity W e will show another proven case of this thesis every problem in L 	th e 
class of problems solvable using logarithmic space	 can be solved extremely e
ciently in parallel 
This is one source of interest in the complexity class L Another source is that this complexity 
class is the basis for the natural reduction that helps to distinguish among the problems in P in 
order to provide a notion of a hardest problem in P 

Logarithmic space 

The most general restriction on the space complexity of a language L that is known to imply 
that L P is logarithmic space Observe that L NL P where the last inclusion follows	 for 
example	 from Theorem The typical use of logarithmic space is to store a constant n umb e r 
of pointers	 eg the names of a constant n umber of nodes in the input graph	 and in some sense	 
this restriction attempts to characterize such algorithms Although L contains many i n teresting 
examples	 we see the role of logarithmic space computation more as a natural means of reduction 
rather then providing interesting algorithms Instead	 we will focus on the nondeterministic and 
randomized analogues	 for which there are languages that appear to be best characterized in terms 
of their space complexity 

To de
ne the notion of a logarithmicspace reduction	 we i n troduce a variant of logarithmic 
space computation that can produce output of superlogarithmic size We s a y that a function f 
can be computed in logarithmic space if there exists a Turing machine with a readonly input 
tape and a writeonly output tape that	 on input x halts with fx written on its output tape and 
uses at most logarithmic space on its work tapes A problem L reduces in logarithmic space 
to L if there exists a function f computable in logarithmic space that maps instances of L into 
instances of L such that x is a yes instance of L if and only if fx i s a y es instance of L 
Let L lo g L denote such a logarithmicspace reduction 􀀀or logspace reduction	 for short It is 
fairly easy to show that the lo g relation is transitive A problem L is NL 
complete if L N 
and for all L NL L lo g L The transitivity o f lo g yields the following result 

Theorem For any NL complete problem LL L if and only if L NL 

Savitch p r o vided the most natural example of an NL complete language the directed graph reach 
ability problem The problem is clearly in NL and can be shown to be NL complete along the 
same lines as the P SP A CE completeness of the circuitbased directed reachability problem 

Theorem The directed graph reachability problem is NL complete 

In view of the above result	 it was very surprising when Alelunias	 Karp	 Lipton	 Lov!asz Racko 

showed that the undirected graph reachability problem the analogue of the directed 
graph reachability problem for undirected graphs	 can be solved by a randomized Turing machine 
using logarithmic space The algorithm attempts to 
nd the required path by following a random 
walk in the graph	 starting from the node s It can be shownthatarandom walk isexpected to use 
every edge with the same frequency and if s and t are in the same connected component t h e n t h e 
walk is expected to reach t in at most O nm steps	 where n and m denotesthe number ofnodes 
and edges We de
ne the class RL to be the logspace analogue of RP A language L is in RL 


if there exists a randomized Turing Machine RM that works in logarithmic space	 such that each 
input x that RM accepts along any computation path is in L and for every xL the probability 
that RM accepts x is at least 

Theorem Undirected graph reachability i s i n RL 

Note added in galleys Recently another piece of evidence has been discovered that suggests that 
undirected graph reachability is easier than its directed analogue Nisan Szemeredi Wigderson 
proved that the undirected graph reachability problem can be solved in D SPACE 􀀀log n 

One can think of the classes L and NL as lowerlevel analogues of P and NP By studying the 
relationships of LN L and co NL one hopes to better understand the relationship of deterministic 
and nondeterministic computation It is this point of view that makes the following theorem of 
Immerman and Szelepcsenyi one of the biggest surprises in recent d e v elopments in 
complexity theory 

Theorem NL co NL 

The proof uses a de
nition of nondeterministically computing a function W e s a y that a function 
fx can be computed in nondeterministic logarithmic space if there is a nondeterministic 
logspace Turing machine that	 on input x outputs the value fx on at least onebranch of the 
computation and on every other branch either stops without an output or also outputs fx If 
fx is a Boolean function	 then we s a y that the language L de
ned by fx is decided in 
nondeterministic logarithmic space 	w hich is equivalent to L being in NL co NL 

We will prove Theorem by showing that the NL complete directed graph reachability 
problem can be decided in nondeterministic logarithmic space Given a directed graph G VA 
a source node s and an integer k 	le t fGsk denote the number of nodes reachable from the 
node s along paths of length at most k 

Lemma The directed graph reachability problem is decidable in nondeterministic logarith 
mic space if and only if the function fGsk can be computed in nondeterministic logarithmic 
space 

Proof To prove the only if direction	 we use the fact that the directed graph reachability i s NL 
complete If it is decidable in logarithmic space	 then so is the problem to recognize if there is a 
path of length at most k T o compute fGsk we use the assumed nondeterministic machine for 
each node v to decide if v is reachable from s by a path of length at most k andcount the number 
of reachable nodes 

To prove the opposite direction	 we use the following nondeterministic logspace computation 
First compute fGsn Thenforeach n o d e v nondeterministically try to guess a path from s 
to v C o u n t the number of nodes for which a path has been found If a path has been found to t 
we accept the input If fGsn nodes have been reachedwithout 
ndingapathto t this proves 
that t is not reachable from s 	s o w e reject Finally 	i f t h e n umber of nodes that have been reached 
is less than fGsn then this is an incorrect branch of the computation	 and the computation 
stops without producing an output 
􀀀 



To nish the proof of Theorem we h a ve to argue that the function fGsk can be computed 
in nondeterministic logarithmic space This is done by induction on k Given fGsk w e can 
decide if there exists a path of length k from s to a particular node v by c hecking if there is a 
path of length at most k to any of the predecessors of v using a variant of the algorithm given in 
the ifpart of Lemma Counting these nodes gives fGsk 

The hardest problems in P 

One important application of logspace computation was introduced by Cook	 who used log 
space reducibility t o i n troduce a notion of a hardest problem in P A problem L is P 
complete if 
L P and for all L P L lo g L The transitivity of the logspace reduction gives the following 
theorem 

Theorem For any P complete problem LL L if and only if LP 

Later in this section we shall see that P completeness also provides evidence that a problem cannot 
be e
ciently solved in parallel This fact has greatly increased the interest in P completeness and 
a v ariety of problems have been shown to be P complete Perhaps the most natural example is the 
circuit value problem	 which w as proved P complete by Ladner Given a circuit with truth values 
assigned to its input gates	 the circuit value problem is to compute the output of the circuit 
This problem is clearly in P It can be proved P complete by building a circuit that simulates the 
computation of a Turing machine 

Theorem The circuit value problem is P complete 

Dobkin	 Lipton Reiss proved that each problem in P logspace reduces to the linear pro 
gramming problem	 and the celebrated result of Khachiyan showed that it is in P Valiant g a ve 
a straightforward reduction from a restricted circuit value problem that uses linear constraints to 
trace the value computed by the circuit 

Goldschlager	 Shaw Staples showed that the maximum ow problem an important special 
case of the linear programming problem	 is also P complete In this problem	 we are given a directed 
graph G VA w i t h t wo speci
ed nodes	 the source s and the sink t and a nonnegative capacity 
ua assigned to each arc aA A feasible ow i s a v ector f RA that satis
es the capacity 
constraints	 ie fa ua for eacharc aA and the ow conservation constraints	 ie 
thesum ofthe ow valuesonthearcsincident to a node v st is the same as the sum of the 

PP

ow v alues on the arcs incident from v Thevalue ofa ow is avt Afa a tvAfa 
The decision problem that is proved to be P complete is deciding the parity of the maximum ow 
value 

There is a collection of P complete problems that are related to simple polynomialtime algo 
rithms The maximal stable set problem in which the objective is to nd a maximal not 
maximum stable set in an undirected graph	 can clearly be solved by a simple greedy algorithm 
When using this procedure	 we usually select the 
rst available node in each step	 and so we 
nd 
a speci
c solution	 the lexicographically
rst one Cook showed that 
nding the lexicographically 


rst maximal stable set is P complete This result might be surprising since this problem is easy to 
solve in polynomial time However	 P completeness also provides evidence that the problem is not 
solvable e
ciently in parallel Consequently this completeness result supports the intuition that 
the greedy algorithm is inherently sequential 


Parallel computation 

Parallel computation gives us the potential of substantially increasing the size of the instances 
for which certain problems are manageable by solving them with a large number of processors 
simultaneously In studying parallel algorithms	 we shall not be concerned with the precise numb e r 
of parallel processors used	 but rather their order as a function of the input size We s a y that 
a parallel algorithm using Opn processors achieves optimal speedup if it runs in Otn 
time and the best sequential algorithm known for solving the same problem runs in Otnpn 
time E
cient algorithms that reach optimal or near optimal speedup with a signi
cant n umb e r 
of processors have been found for many of the basic combinatorial problems Another aspect 
of parallel computation is concerned with the inherent limitations of using many processors to 
speed up a computation To be somewhat realistic	 we shall only be interested in algorithms that 
use a polynomial number of processors Consequently 	w e will focus on the possible speedup of 
polynomialtime sequential computation by parallel processing 

First we de
ne a model of parallel computation Although many such m o d e l s h a ve been pro 
posed	 one that seems to be the most convenient for designing algorithms is the parallel random 
access machine PRAM The PRAM is the parallel analogue of the random access machine 
it consists of a sequence of random access machines called processors	 each with its own in
nite 
local random access memory in addition to an in
nite shared random access memory where each 
memory cell can store any i n teger	 and the input is stored in the shared memory Each processor 
knows the input size and its identi
cation number	 although otherwise the processors are identical 

ie they run the same program Dierent v ariants of the basic PRAM model are distinguished by 
the manner in which they handle read and write conicts In an EREW PRAM 􀀀exclusiveread 
exclusivewrite PRAM	 for example	 it is assumed that each cell of the shared memory is only 
read from and written into by at most one processor at a time At the other extreme	 in a CRCW 
PRAM 􀀀concurrentread	 concurrentwrite PRAM	 each cell of the memory can be read from and 
written into by more than one processor at a time If dierent processors attempt to write dierent 
things in the same cell	 then the lowest numbered processor succeeds 

To illustrate the power of parallel computation	 we give parallel algorithms for a problem that 
we h a ve already discussed Although 
nding the lexicographically
rst maximal stable set is P 
complete	 Karp Wigderson have proved	 surprisingly that a maximal stable set can be found 
e
ciently in parallel Similar	 much simpler and more e
cient randomized algorithms have subse 
quently been independently discovered by Luby and by Alon	 Babai Itai 

Consider the most natural sequential algorithm for the problem select a node v and include it 
in the stable set	 delete v and all of its neighbors from the graph repeat this procedure until all 
nodes have been deleted Note that this algorithm requires n iterations for a path of length n A 
similar approach can still be used for a parallel algorithm To m a k e the algorithm fast	 one selects 
a stable set in each iteration 􀀀rather than a single node	 where the set is deleted along with its 
neighb o r h o o d The following simple way t o c hoose this stable set is due to Luby A processor is 
assigned to each node and each edge of the graph For a graph of order n the processor assigned 
to node v picks a random integer cv from to n Next	 each processor assigned to an edge 
compares the values at the two nodes of the edge The stable set selected consists of those nodes 
v for which cv is strictly larger than the values assigned to any of its neighb o r s 

This algorithm clearly 
nds a maximal stable set	 but it is less clear that few iterations are 


needed It can be shown that each iteration is expected to remove a constant fraction of the 
edges	 and consequently theexpected number of iterations is O 􀀀log n The algorithm can be 
implemented on a randomized CRCW PRAM in O 􀀀log n time 􀀀if we assume that a processor can 
choose a random number of size O 􀀀log n in one step 

Karp Wigderson introduced a technique that can be used to convert certain randomized 
algorithms into deterministic ones The technique can be used if	 in the analysis of the randomized 
algorithm	 it is not necessary to assume mutual independence	 but	 for example	 d wise independent 
choices su
ce for some constant d One can appeal to known constructions to show that such 
variables can be chosen from a sample space of polynomial size Each iteration can then be run for 
each p o i n t in the sample space simultaneously and this ensures that a good sample point i s u s e d 
This method can be used to convert the above randomized algorithm into a deterministic one 

When discussing parallel algorithms we shall assume that all arithmetic operations are restricted 
to polynomialsize numbers	 and the number of processors used is polynomially bounded We de
ne 
the class NC to consist of all languages L for which there exists a parallel algorithm that runs in 
time bounded by a polynomial in log n Note that in this de
nition the distinction between the 
dierent v ersions of the basic PRAM model are not relevant If a problem can be solved by a C R CW 
PRAM using pn processors in O 􀀀logi n time	 then it can be solved by an EREW PRAM using 
pn processors and O 􀀀logi n log pn time The maximal stable set algorithm of Luby discussed 
earlier uses a randomized version of the CRCW PRAM We de
ne the complexity class RNC to 
be the NC analog of RP 

It is straightforward to see that Boolean product of two nn matrices can be computed 
in constant time on a CRCW PRAM using On processors By repeatedly squaring the adjacency 
matrix of a graph	 the directed reachability problem can be solved in O 􀀀log n time This is	 in some 
sense	 the generic problem in NL and more generally 	a n y problem in NL canbe solvedby a C R CW 
PRAM in O 􀀀log n time As a consequence	 a logspace reduction can be simulated e
ciently in 
parallel	 and therefore P completeness provides evidence that a problem is not e
ciently solvable 
in parallel 

Theorem For any P complete problem LL NC if and only if NC P 

We get the following chain of inclusions 

L NL NC P NP PSPACE 

On the other hand	 the computation of a CRCW PRAM that runs in O 􀀀logi n time can be simulated 
by a T uring machine in O 􀀀logi n space This proves that NC is contained in i D SPACE 􀀀logi n 
By the analogue of Theorem for space complexity this implies that N C PSPACE 

We h a ve already seen that a simple parallel algorithm for the directed reachability problem is 
based on matrix multiplication	 and in fact	 many simple parallel graph algorithms are based on 
matrix operations Csanky has given an NC algorithm to compute the rank and the determinant 
of a matrix over the reals in O 􀀀log n t i m e As a corollary 	w e get a parallel algorithm to solve 
systems of linear equations Berkowitz	 Chistov and Mulmuley have extended these results to 
matrices over arbitrary 
elds One of the most beautiful connections between matrix operations 
and graph algorithms is that a perfect matching in a graph can be found by an e
cient randomized 
parallel algorithm using only a single matrix inversion 􀀀see Chapter 


There has been substantial work over the past several years in 
nding e
cient parallel algorithms 
for combinatorial problems Some of these algorithms are mentioned elsewhere in this Handbook 
For further results and more details the interested reader is referred to the survey of Karp 
Ramachandran 

Acknowledgments 

In writing this survey 	w e h a ve often been aided by the expertise of others In particular	 we 
would like to thank Laci Babai and Michael Sipser for sharing with us many of their insights into 
complexity theory The surveys that we h a ve cited in particular areas of complexity theory were 
extremely useful and we wish express our gratitude to their authors In addition	 we w ould like 
to thank Sha
 Goldwasser	 Leslie Hall	 David Johnson	 Jan Karel Lenstra	 Laci Lov!asz	 Albert 
Meyer	 Carolyn Haibt Norton and Larry Stockmeyer for their many insightful comments on an 
earlier draft The research of the 
rst author was supported in part by an NSF Presidential Young 
Investigator award CCR" with matching support from IBM	 UPS and Sun and by A i r 
Force Contract AFOSR"" The research of the second author was supported in part by A i r 
Force Contract AFOSR"" and by a P ackard Research F ellowship Both were supported in 
part by the National Science Foundation	 the Air Force O
ce of Scienti
c Research	 and the O
ce 
of Naval Research	 through NSF grant DMS" 


References 

Aho A V J E Hopcroft and J D Ullman 
The Design and Analysis of Computer Algorithms Addison)Wesley Reading	 
Massachusetts 

Alelunias R R M Karp R J Lipton L Lovasz and C Rackoff 
Random walks	 universal traversal sequences	 and the complexity of maze problems	 
in Proceedings of the th Annual IEEE Symposium on Foundations of Computer 
Sciences IEEE Computer Society Press	 Washington	 DC pp 

Babai L 

Trading group theory for randomness	 in Proceedings of the th Annual ACM 
Symposium on Theory of Computing A CM Press	 New York	 NY pp 
Baker T J Gill and R Solovay 
Relativizations of the P NP question	 SIAM J on Comput 
Chandra A K D C Kozen and L J Stockmeyer 
Alternation	 J Assoc Comput Mach 

Cobham A 

The intrinsic computational di
culty of functions	 in Proceedings of the 
International Congress for Logic Methodology and Philosophy of Science edited by 
Y Bar)Hillel	 􀀀North)Holland	 Amsterdam pp 

Coffman Jr E G G S Lueker and A H G Rinnooy Kan 
Asymptotic methods in the probabilistic analysis of sequencing and packing 
heuristics	 Management Sci 

CookS A 

The complexity of theorem)proving procedures	 in Proceedings of the rd A nnual ACM 
Symposium on Theory of Computing A CM Press	 New York	 NY pp 

Davis M 

Unsolvable problems	 in Handbook of Mathematical Logic edited by J Barwise 
􀀀North)Holland	 Amsterdam pp 

Edmonds J 

Paths	 trees and owers	 Canad J Math 

Fischer M J and M O Rabin 
Super)exponential complexity of Presburger arithmetic	 in Complexity of 
Computation SIAM)AMS Proceedings	 Vol edited by R M Karp	 􀀀American 
Mathematical Society 	P r o vidence	 Rhode Island pp 

Furst M J B Saxe and M Sipser 
Parity circuits	 and the polynomial)time hierarchy Math Systems Theory 

Garey M R and D S Johnson 
The complexity of near)optimal graph coloring	 J Assoc Comput Mach 
Computers and Intractability
 A Guide to the Theory of NPCompleteness WH 
Freeman and Co	 San Francisco 

Godel K 

Uber formal unentscheidbare Satze der Principia Mathematica und verwandter 
Systeme	 I	 Monatsh Math Phys 


Goldwasser S 

Interactive proof systems	 in Computational Complexity Theory AMS Symposia in Applied 
Mathematics	 	e d i t e d b y J Hartmanis 􀀀AMS	 Providence	 Rhode Island	 pp 
Goldwasser S S Micali and C Rackoff 
The knowledge complexity o f i n teractive proof)systems	 SIAM J Comput 

Graham R L 

Bounds for certain multiprocessing anomalies	 Bell System Tech J 
Hartmanis J and R E Stearns 
On the computational complexity of algorithms	 Trans Amer Math Soc 

Hopcroft J W Paul and L Valiant 
On time versus space	 J Assoc Comput Mach 

Hopcroft J E and J D Ullman 
Introduction to Automata Theory Languages and Computation Addison)Wesley 
Reading	 MA 

Immerman N 

Nondeterministic space is closed under complementation	 SIAM J Comput 

Johnson D S 

The NP)Completeness Column An Ongoing Guide	 J Algorithms 
The NP)Completeness Column An Ongoing Guide	 J Algorithms 
The NP)Completeness Column An Ongoing Guide	 J Algorithms 

KarpR M 

Reducibility among combinatorial problems	 in Complexity of Computer 
Computations editedby R E M illerand J W Thatcher	 􀀀Plenum Press	New 
York pp 
The probabilistic analysis of some combinatorial search algorithms	 in Algorithms 
and Complexity
 New Directions and Recent Results 	edited by J F Traub	 

􀀀Academic Press	 New York pp 

Karp R M J K Lenstra C J H McDiarmid and AHGRinnooy K an 
Probabilistic analysis	 in Combinatorial Optimization
 Annotated Bibliographies 
edited by M O hEigeartaigh	 J K Lenstra and A H G Rinnooy Kan 􀀀Centre 
for Mathematics and Computer Science	 Amsterdam and John Wiley Sons	 
Chichester pp 

KarpR M and V Ramachandran 
Parallel algorithms for shared)memory machines	 in The Handbook of Theoretical 
Computer Science Volume A Algorithms and Complexity edited by 
J van Leeuwen 􀀀Elsevier	 Amsterdam pp 

van Leeuwen J editor 
Handbook of Theoretical Computer Science 􀀀Elsevier	 Amsterdam 

Lenstra A K and H W Lenstra Jr 
Algorithms in number theory 	i n The Handbook of Theoretical Computer Science 
Volume A Algorithms and Complexity 	edited by J vanLeeuwen 

􀀀Elsevier	 Amsterdam pp 

Levin L A 

Universal sequential search problems	 Problemy Peredachi Informatsii in Russian 


#English translation Problems in Information Transmission 
Average case complete problems	 SIAM J Comput 

Meyer A R and L J Stockmeyer 
The equivalence problem for regular expressions with squaring requires exponential 
time	 in Proceedings of the th Annual Symposium on Switching and Automata 
Theory IEEE Computer Society P r e s s W ashington	 DC pp 

Paul W J N Pippenger E Szemeredi and W T Trotter 
On determinism versus nondeterminism and related problems	 in Proceedings of 
the th IEEE Symposium on Foundations of Computer Science IEEE 
Computer Society P r e s s W ashington	 D C pp 

Savitch W J 

Relationships between nondeterministic and deterministic tape complexities	 

J Comput System Sci 

Shamir R 

The e 
ciency of the simplex method a survey Management Sci 

Stockmeyer L J 

Classifying the computational complexity of problems	 J Symbolic Logic 

Szelepcsenyi R 

The method of forcing for nondeterministic automata	 Bull European 
Assoc Theoret Comput Sci 

Turing A M 

On computable numbers	 with an application to the Entscheidungsproblem	 

Proc London Math Soc II 

Valiant L G 

The complexity of computing the permanent	 Theoret Comput Sci 

Yao ACC 

Separating the polynomial)time hierarchy b y oracles	 in Proceedings of the 
th 
Annual IEEE Symposium on Foundations of Computer Science IEEE Computer 
Society P ress W ashington	 DC pp