Computational Complexity

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 five.

Chudnovsky's web page now has papers describing all of these results as well as other pointers on perfect graphs.

1:12 PM # Comments []   

Monday, February 17, 2003

 
Complexity Class of the Week: BPP_path

Previous CCW

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

1. If x is in L then there are at least twice as many accepting as rejecting paths of M(x).
2. If x is not in L then there are at least twice as many rejecting as accepting paths of M(x).

Suppose we use the same definition without the "balanced" requirement. This gives us the class BPP_path studied mostly in a 1997 paper of Han, Hemaspaandra and Thierauf.

BPP_path contains BPP by definition but it contains much more. Let us show that SAT is contained in BPP_path.

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 accept.

If φ is not satisfiable then M(φ) will only have rejecting paths. If φ is satisfiable then it will have at least 2ⁿ⁺¹ accepting paths and at most 2ⁿ-1 rejecting paths fulfilling the requirements of the definition of BPP_path.

Han, Hemaspaandra and Thierauf prove many other results about BPP_path. The class contains MA and P^NP[log] (P with O(log n) queries to an NP language like SAT). BPP_path is contained in P^Σ₂[log], BPP^NP and PP.

Whether BPP_path is contained in ZPP^NP or Σ₂ remain the most interesting open questions about this class.

10:05 AM # Comments []   

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 "expensive." The variation 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.

10:11 AM # Comments []   

Archives