Howdy from Berlin

I'm writing from the STACS conference, one of my favorite European conferences. Next week I'll be in Holland visiting CWI and talking at the NVTI Theory Day.

Far less Americans than usual this year. While European travel is definitely down (my plane was quite empty), scientists are usually not deterred by political events. More likely is the drop in grant money forcing researchers to be more picky in their choice of conferences. This year the Complexity Conference is in Europe as well.

Also far less French than usual, STACS being a joint French-German conference. I have no explanation for this.

This is not a science item but interesting nevertheless: I had to rebook my flight back; the US government needed the plane to "fight terrorism", most likely to ferry troops to the Gulf.

There have been some interesting talks at the conference. I'll try to mention some of them when I get a chance.

A Zero-One Law for RP

Russell Impagliazzo and Phillipe Moser have an upcoming Complexity paper entitled A Zero-One Law for RP. What does that mean?

Jack Lutz defined a notion of resource-bounded measure to find the relative size of complexity classes within exponential time. He has many surveys and research papers available on this interesting topic. Whether NP has measure zero in EXP is the most exciting open question in this area.

Dieter van Melkebeek noted that the Impagliazzo-Wigderson derandomization results implied a zero-one law for BPP: Either BPP=EXP and has measure one or there is sufficient derandomization to show BPP has measure zero.

The ideas do not directly work for the one-sided error class RP. The new Impagliazzo-Moser paper shows how to overcome these difficulties to get the zero-one law for RP. They also show that if RP does not have measure zero then not only RP but ZPP is equal to EXP. They also show some new derandomization if NP does not have measure zero, i.e., to get that AM = NP.

Complexity Papers Announced

The list of accepted papers for the 18th Annual IEEE Conference on Computational Complexity is now available. The conference will be held July 7-10 in Århus, Denmark and based on the titles of the accepted papers it should be an exciting meeting.

I will talk about a few of the more interesting papers in the weeks ahead. For now you can download many of these papers from the authors' web pages or from the ECCC.

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.

Complexity Class of the Week: BPPpath

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.

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.

Traveling Salesman on the Plane

Yesterday's post on NP-complete problems reminds me of one of the more interesting open questions, the complexity of the traveling salesman problem on the plane.

The traveling salesman problem consists of a collection of n cities, a symmetric distance function d(i,j) and a number k. The question is whether there is an ordering of the cities so that a tour through those cities and back to the start can be done in total distance at most k. If d takes on rational values, the problem is NP-complete in general and for many restrictions of the possible functions for d, such as requiring d to have the triangle inequality.

Consider the case where the cities are given as points (x,y) in the plane and the distance function is the regular Euclidean distance, i.e.,

d((r,s),(u,v))=((r-u)²+(s-v)²)^1/2. It is open whether this traveling salesman problem on the plane is NP-complete. In most cases, it is easy to show the problem is in NP and more difficult to show it NP-hard. For TSP on the plane, Garey, Graham and Johnson showed it NP-hard way back in 1976; it remains open whether the problem is in NP.

In NP one can guess the ordering of the cities, the problem is in checking whether the sum of distances is at most k. Since we can approximate the square root to a polynomial number of digits the issue is how many digits of accuracy we need. So it boils down to the following purely mathematical question: Given an expression of length m over integers with addition, subtraction, squares and square roots (but no recursive squares or square roots) what is the smallest positive number than can be expressed? If the answer is at least 2^-mk for some k then TSP on the plane is in NP and NP-complete.

Let me also mention that one can well approximate traveling salesman on the plane.

Foundations of Complexity Lesson 15: More NP-complete Problems

Previous Lesson | Next Lesson

Now that we have shown that CNF-SAT is NP-complete we can use it to show many other problems are NP-complete via the following lemma.

Lemma: If a set A is NP-complete and B is in NP and A polynomial-time reduces to B then B is also NP-complete.

Proof: Let C be an arbitrary set in NP. We need to show C reduces to B. We know C reduces to A (since A is complete) and A reduces to B and it is a simple exercise to see that reductions are transitive. ◊

For example consider 3-SAT, the set of satisfiable 3-CNF formula with exactly 3 literals in each clause. 3-SAT is in NP by just guessing an assignment and verifying that it satisfies the formula. To show 3-SAT is NP-complete we will reduce 3-CNF to 3-SAT. We take each clause and convert it to a set of clauses each with three literals. We will add additional variables for this reduction.

If the clause C has three literals then no conversion is necessary.

If the clause C has two literals something like C = x OR y. We use a new variable z and replace C with two clauses, x OR y OR z and x OR y OR z. Notice that C is satisfied if and only if both new clauses can be satisfied.

If the clause C has one literal like C = x, we add two new variables, u and v and replace C with four new clauses, x OR u OR v, x OR u OR v, x OR u OR v and x OR u OR v.

If the clause C has k literals for k>3, we will replace C by two clauses, one with k-1 literals and one with 3 literals and then recurse. Suppose C = x₁ OR ... OR x_k. We add a new variable w and replace C with X₁ OR ... OR X_k-2 OR w and w OR x_k-1 OR x_k. Again note that C is satisfied only if both of the new clauses are satisfied with some value for w.

That is the reduction and the proof that it works is straightforward.

There are many many natural NP-complete problems and we could spend many lessons showing that they are NP-complete. Personally, I find NP-completeness proofs more algorithmic than complexity and I will instead focus on relationships of complexity classes in future lessons.

This site is a collection of optimization problems but it also gives you a good idea of what NP-complete problems are out there. The best source for all things NP-complete still remains the excellent book of Garey and Johnson.

NEXP not in P/poly?

Daniel Varga asks about the question of NEXP not in P/poly and whether it is "fundamentally" easier than NP not in P/poly. As a reminder: NEXP is the class of languages accepted in nondeterministic exponential (2^nO(1)) time. P/poly are languages accepted by nonuniform polynomial-size circuits, or equivalently by a polynomial time machine given a polynomial amount of "advice" that depends only on the input size.

First one must mention the beautiful paper of Impagliazzo, Kabanets and Wigderson that show that NEXP in P/poly if and only if NEXP equals MA.

NEXP not in P/poly should be much easier to prove than NP not in P/poly, as NEXP is a much larger class than NP. Also NEXP not in P/poly is just below the limit of what we can prove. We know that MA_EXP, the exponential time version of MA, is not contained in P/poly. MA_EXP sits just above NEXP and under some reasonable derandomization assumptions, MA_EXP = NEXP.

There is also the issue of uniformity. If one can use the nondeterminism to reduce the advice just a little bit than one could then diagonalize against the P/poly machine. Also if one could slightly derandomize MA machines than one could diagonalize NEXP from MA and thus from P/poly.

Still the problem remains difficult. BPP is contained in P/poly and we don't even know whether BPP is different than NEXP. Virtually any weak unconditional derandomization of BPP would separate it from NEXP but so far we seem stuck.

JACM is 50

For those with access to the Journal of the ACM, the fiftieth anniversary issue (Volume 50, Number 1) has a number of very short articles by prominent computer scientists on a number of interesting research issues in CS. In particular, articles by Steve Cook, Juris Hartmanis, Alexander Razborov, Peter Shor, Richard Stearns, Les Valiant and Andy Yao talk about problems directly related to this web log.

Yao's article "Classical Physics and the Church-Turing Thesis" is also available from ECCC. He makes some arguments (that I don't necessarily agree with) that there are some physical systems where Turing machines fail to capture computation.

While I was gone

The list of accepted papers of STOC has been posted. STOC and FOCS are the two most important annual theoretical computer science conferences. Quite a few interesting complexity papers. You can often download them by going to the authors' web sites.

From Scott Aaronson: I gave a talk to my brother's high school math club called "The Prime Facts: From Euclid to AKS." A writeup is available in case readers of your weblog are interested.

Last, but not least, we all are very saddened by the Columbia shuttle tragedy and the loss of seven brave people in the pursuit of science.