This work is licensed under a
Creative Commons License.
|
Friday, February 28, 2003
Howdy from Berlin
Posted by Lance
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.
4:36 AM #
Tuesday, February 25, 2003
A Zero-One Law for RP
Posted by Lance
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.
2:50 PM #
Monday, February 24, 2003
Complexity Papers Announced
Posted by Lance
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.
1:03 PM #
Friday, February 21, 2003
More on Perfect Graphs
Posted by Lance
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 #
Monday, February 17, 2003
Complexity Class of the Week: BPPpath
Posted by Lance
Previous CCWLet 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 accept.
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 BPPpath.
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 PP.
Whether BPPpath is contained in ZPPNP or Σ2 remain the most interesting open questions about this class.
10:05 AM #
Sunday, February 16, 2003
News for Nerds. Stuff that Matters.
Posted by Lance
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 #
Friday, February 14, 2003
Traveling Salesman on the Plane
Posted by Lance
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)2+(s-v)2)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.
10:01 AM #
Thursday, February 13, 2003
Foundations of Complexity
Lesson 15: More NP-complete Problems
Posted by Lance
Previous Lesson | Next LessonNow 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 = x1 OR ... OR xk. We add a new variable w and replace C with X1 OR ... OR Xk-2 OR w and w OR xk-1 OR xk. 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.
9:53 AM #
Tuesday, February 11, 2003
NEXP not in P/poly?
Posted by Lance
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 (2nO(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 MAEXP, the exponential time version of MA, is not contained in P/poly. MAEXP sits just above NEXP and under some reasonable derandomization assumptions, MAEXP = 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.
4:05 PM #
Wednesday, February 05, 2003
JACM is 50
Posted by Lance
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.
4:12 PM #
Monday, February 03, 2003
While I was gone
Posted by Lance
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.
11:34 AM #
Archives
