### Friday, August 30, 2002

**Great Books:** Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson.
Despite that 23 years have passed since its publication, I consider Garey and Johnson the single most important book on my office bookshelf. Every computer scientist should have this book on their shelves as well. NP-completeness is the single most important to come out of theoretical computer science and no book covers it as well as Garey and Johnson.

The popularity of the book comes mainly from its appendix that consumes nearly half the pages. This section gives a comprehensive list of NP-complete problems in a well-structured and organized fashion. If one needs to determine whether a problem X is NP-complete, one can almost always either find X in the appendix or find a Y in the appendix that easily reduces to X. And the name-instance-question format has inspired many imitators, for example P-completeness and NP optimization.

It would be a mistake to ignore the first half of the book. Garey and Johnson has the best introduction to computational complexity I have ever seen. It gives basic proofs of NP-completeness results but more importantly gives the tools one needs to generate new NP-complete proofs. Section 6 discusses issues about what to do if one *has* to write an algorithm for an NP-complete problem. Section 7 discusses many different advanced concepts in complexity that give a taste to the richness of the area. And don't miss the terminological history in Section 5.2.

Of course Garey and Johnson misses the last 23 years of research. Many more NP-complete problems are known. Linear Programming and Composite Number are listed as open questions. The results on hardness of approximation based on probabilistically checkable proofs came long after the publication of the book. Section 7, "Beyond NP-completeness" is woefully out of date. Nevertheless no book before or since has captured the critical NP-completeness concept better than this classic book.

7:54 AM
#
Comments
[]

### Wednesday, August 28, 2002

**Complexity Class of the Week: S**_{2}^{P}

CCW Intro
Suppose a polynomial-time computable judge has to decide whether a
string is in a language. Two lawyers submit written arguments to
convince the judge, one arguing for the string in the language and the
other arguing for the string to be out of the language. Neither lawyer
can see the others arguments. For what languages can we have the judge
always convinced?

Russell
and Sundaram define the class S_{2}^{P} to capture this notion. Formally
a language L is in S_{2}^{P} if there is a polynomial-time predicate A and
a polynomial q such that

- If x is in L then there is a y such that for all z, A(x,y,z).
- If x is not in L then there is a z such that for all y, not
A(x,y,z).

where |y| and |z| are bounded by q(|x|). Personally I like to think
of S_{2}^{P} as for every input x defining an
exponential binary matrix A where the (i,j) entry of A is computable
in polynomial time from i,j and x. If x is in the language then A has
a row of all ones. If x is not in the language then A has a column of
all zeros.

NP∪coNP is in S_{2}^{P} is in
Σ_{2}^{P}∩Π_{2}^{P}.
Russell and Sundaram show that S_{2}^{P} is closed
under Turing reduction and relativizations to BPP. This implies BPP,
MA and P^{NP} are contained in S_{2}^{P}.

A big breakthrough for S_{2}^{P} comes from Cai
who shows that S_{2}^{P} is contained in
ZPP^{NP}. His proof is builds on the learning
algorithm of Bshouty, et. al. Sengupta noticed that a variation
of the
Karp-Lipton result shows that if NP has polynomial-size circuits
then the polynomial-time hierarchy collapses to
S_{2}^{P}. This also improves Kannan's
result to show that for any fixed k, there is a language in
S_{2}^{P} that does not have n^{k}-size
circuits. S_{2}^{P} is the smallest class known to have these properties.

S_{2}^{P} has come up recently in several of my research projects. Beigel,
Buhrman, Fejer, Fortnow, Longpre, Stephan and Torenvliet show that
a language L is in S_{2}^{P} if and only if there is a function f mapping
Σ^{*} to {1,2,3} such that L is polynomial-time Turing
reducible to all 2-enumerators for f. Buhrman and Fortnow give an
oracle separating ZPP^{NP} from Σ_{2}^{P}∩Π_{2}^{P} which by Cai's result
gives the first relativized world separating S_{2}^{P} from
Σ_{2}^{P}∩Π_{2}^{P}. Fortnow, Pavan and Sengupta show that if P^{NP[2]} =
P^{NP[1]} then the polynomial-time hierarchy collapses to
S_{2}^{P} improving on earlier collapses. You will have to trust me on the
latter two results as they are in the process of being written up.

Whether S_{2}^{P} contains ZPP^{NP} is open
even for relativized worlds. Since AM∩coAM is in ZPP^{NP},
one could try to prove that AM∩coAM is in
S_{2}^{P} or a specific language in AM∩coAM such
as graph isomorphism.

There are variations on the class S_{2}^{P} and I
recommend reading the papers of Russell
and Sundaram and Cai
for these and other results about this interesting class.

2:07 PM
#
Comments
[]

### Tuesday, August 27, 2002

**Complexity Class of the Week**
When I was at U. Chicago, we would have a semiregular feature call the
*Complexity Class of the Week* where we would pick a complexity
class or other concept and on a white board in the lounge write the
definition, what was known, how it related to other classes and
perhaps most importantly what open questions remained.

I decided to
revive this tradition here on this virtual whiteboard in the ultimate
lounge known as the internet.

Scott Aaronson has set up a Complexity
Zoo that gives a short description of many classes that make a
good reference. We will go more in depth for a single class or concept
but Aaronson's site makes for a good reference for other classes we
mention.

Watch this space tomorrow for the first complexity class of the
week. Feel free to email me with suggestion for future classes of the
week, especially if you are willing to contribute a write-up.

4:13 PM
#
Comments
[]