Friday, February 21, 2003
More on Perfect Graphs
Today I saw Maria Chudnovsky give a talk at Princeton on her new result with
Paul Seymour finding a polynomial-time algorithm for testing perfect
graphs, a result I mentioned
in an earlier post. The algorithm actually tests for Berge graphs
which are graphs with no induced odd cycle of length at least five or
the complement of such a graph. An earlier result of Chudnovsky,
Robertson, Seymour and Thomas showed that a graph is perfect if and
only if it is Berge. Otherwise the new algorithm does not use the
techniques of the earlier paper.
The algorithm looks for some basic structures that would imply the
graph is not Berge. If these structures don't exist then one does a
cleaning process that simplifies the search for odd cycles. A
cleaning process is described in another paper by Chudnovsky,
Cornuéjols, Liu, Seymour and Vuškovic.
While the algorithm will test whether the graph is Berge, it is still
open to determine whether a graph had an odd cycle of length at least
page now has papers describing all of these results as well as other
pointers on perfect graphs.
Monday, February 17, 2003
Complexity Class of the Week: BPPpath
Let us call a nondeterministic Turing machine M balanced if for
every input x, all of its computational paths have the same length,
i.e., the number of nondeterministic bits depends only on x and not on
previous guesses. We can define the characterize class BPP as follows:
L is in BPP if there is a balanced nondeterministic polynomial-time M such that
Suppose we use the same definition without the "balanced"
requirement. This gives us the class BPPpath studied mostly
in a 1997
paper of Han, Hemaspaandra and Thierauf.
- If x is in L then there are at least twice as many accepting as
rejecting paths of M(x).
- If x is not in L then there are at least twice as many rejecting
as accepting paths of M(x).
BPPpath contains BPP by definition but it contains much
more. Let us show that SAT is contained in BPPpath.
Let φ be a formula with n variables. Consider the following
machine M(φ): Guess an assignment a for φ. If a is rejecting
then reject. If a is accepting then guess n+1 bits, ignore them and
If φ is not satisfiable then M(φ) will only have rejecting
paths. If φ is satisfiable then it will have at least
2n+1 accepting paths and at most 2n-1 rejecting
paths fulfilling the requirements of the definition of
Han, Hemaspaandra and Thierauf prove many other results about
BPPpath. The class contains MA and
PNP[log] (P with O(log n) queries to an NP language like
SAT). BPPpath is contained in
PΣ2[log], BPPNP and
Whether BPPpath is contained in ZPPNP or Σ2 remain
the most interesting open questions about this class.
Sunday, February 16, 2003
News for Nerds. Stuff that Matters.
I noticed that Slashdot has
recently mentioned some TCS research. This would therefore be
theoretical computer science that matters to nerds.
The first was a pointer to Scienceblog article
on the work of Roughgarden and Tardos on selfish routing. Here is
their main example: Consider two roads from city A to city B. The
first road takes an hour and the second road takes p hours, where p is
the fraction of people who take the second road. The best way to route
to minimize total travel time is for half the people to take the
second road (average time = 3/4 hour). If everyone acts selfishly, the
only equilibrium is everyone taking the second road for an average
time of one hour. For more details see Tim Roughgarden's home page.
The other article pointed to Microsoft's research Penny
Black Project which hopes to prevent spam by making sending email
using complexity requires the sender to solve a moderately hard
problem generated by the intended recipient.
Always keep in mind that what happens at Microsoft research,
especially amongst the theoreticians, should not be read to imply any
future email policy at Microsoft, no more than one can determine
future NEC policies from my own research.