In the 1950's, Friedberg and Muchnik independently showed that there were sets that were computably enumerable, not computable and not complete. Does a similar result hold for complexity theory?

Suppose P≠NP. We have problems that are in P and problems that are NP-complete and we know these sets are disjoint. Is there anything else in NP? In 1975, Ladner showed the answer is yes.

Theorem (Ladner) If P≠NP then there is a set A in NP such that A is not in P and A is not NP-complete.

I wrote up two proofs of this result, one based on Ladner's proof and one based on a proof of Impagliazzo. The write-up is taken mostly from a paper by Rod Downey and myself.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/24/2003 5:26:58 PM

Powered by Blogger Pro

The University of Connecticut defeated BYU in men's basketball yesterday, keeping the integrity of the tree.

If you are a male American, you are likely participating in a pool predicting the outcomes of the games of the NCAA basketball tournament. How are you doing? Have you been eliminated yet? Not such an easy question to answer as it turns out. Six MIT grad students have recently shown it is NP-complete to decide if you can still win the pool.

Dave Pennock pointed out that there have been many articles in the popular press about information markets including a piece in the New Yorker.

Pennock also mentioned the Iowa Electronic Markets, which allows limited legal trading in certain political markets.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/21/2003 2:20:58 PM

Powered by Blogger Pro

Information Markets do information aggregation by creating financial securities based on the outcome of some event. You can then make predictions based on the prices of these securities. For example, look at the Best Actress page of the Hollywood Stock Exchange. There are five securities listed for each of the nominees. Each security will pay out $25 if that nominees wins and $0 otherwise. At the time I am writing this, the price of the Nicole Kidman security is $13.45. If you take the ratio of the price to the final payoff this gives a probability of winning. For Kidman that would be a $13.45/$25 or 53.8% chance of winning the award.

There are two problems with the Hollywood Stock Exchange. First they don't use real money since that would be illegal in the US. Also the best actress winner has already been chosen so if real money were being used there is the potential for corruption. Nevertheless studies have shown that even such artificial markets still do far better than the experts in predicting the winners.

You can eliminate the problems by considering sporting events on real off-shore betting sites. Sites like Tradesports or the World Sports Exchange have securities (futures) on outcomes based on sporting events that you can look at without registering. In Tradesports consider the security NCAA.BK.KENTUCKY that pays off $100 if the University of Kentucky wins the men's basketball championship and $0 otherwise. The price as I am writing has a bid of $25 and an ask of $26 meaning that Kentucky has between a 25% and 26% chance of winning the NCAA tournament. It will be interesting to see the price and thus the odds change as the tournament progresses. For example if Arizona would be upset in an early round, this should cause Kentucky's price to go up.

Tradesports also has securities in entertainment and political events. On Tradesports Kidman has a bid/ask of $54/$57 not too far off of the Hollywood Stock Exchange.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/19/2003 10:04:14 AM

Powered by Blogger Pro

In a usual year the rules are simple. Each team plays its sibling. The winner advances to the parent node and the process repeats. The team that reaches the root is the champion.

The tree structure gives a nice uniqueness factor. If Notre Dame plays Duke this year, they would have to meet in the fourth round. There is no scenario of plays in the other games that would cause Notre Dame to play Duke in any other round.

So why isn't it a tree this year? The problem is Brigham Young University. If BYU wins their first three games, they would have played their fourth game on Sunday, March 30. BYU is a Mormon school and school policy forbids games on Sundays. The NCAA solution is the following: If BYU wins their first two games they would swap with one of the teams from the Midwest subtree which plays its fourth round on Saturday the 29th. In the more likely event that BYU does not win its first two games the original schedule will hold.

It's not hard to show that the uniqueness property above no longer holds and thus the tournament this year no longer can be represented as a tree.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/18/2003 9:52:57 AM

Powered by Blogger Pro

Now with the second war about to start I am not teaching but am in a similar position with respect to this weblog. I will not discuss much about the war in this weblog, there are plenty of other weblogs for that purpose. I will instead keep this weblog going as usual to keep a sense of normalcy and because science, in its pure form, does not depend on the political events of the world.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/17/2003 10:53:38 AM

Powered by Blogger Pro

In my first year as an assistant professor at the University of Chicago, I taught a graduate complexity course where I gave a homework question to show that computing the permanent of a matrix A with nonnegative integer entries is in #P. Directly constructing a nondeterministic Turing machine such that Perm(A) is the number of accepting computations of M(A) is not too difficult and that was the approach I was looking for.

In class we had shown that computing the permanent of a zero-one matrix is in #P so Viktoria Zankó decided to reduce my homework question to this problem. She came up with a rather clever reduction that converted a matrix A to a zero-one matrix B with Perm(A)=Perm(B). This reduction indeed answered my homework question while, unbeknownst to Zankó at the time, answered an open question of Valiant. Thus Zankó got a publication by solving a homework problem the hard way.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/14/2003 8:25:48 AM

Powered by Blogger Pro

Let A={a_ij} be an n×n matrix over the integers. The determinant of the A is defined as

The determinant is computable efficiently using Gaussian Elimination and taking the product of the diagonal.

The permanent has a similar definition without the -1 term. We define the permanent of A by

Unlike the determinant the permanent seems quite hard to compute. In 1979, Valiant showed that the permanent is #P-complete, i.e., computing the permanent is as hard as counting the number of satisfying assignments of a Boolean formula. The hardness of the permanent became more clear after Toda's Theorem showing that every language in the polynomial-time hierarchy is reducible to a #P problem and then the permanent.

The permanent is difficult to compute even if all the entries are 0 and 1. However determining whether the permanent is even or odd is easy since Perm(A) = Det(A) mod 2.

Since we can't likely compute the permanent exactly, can we approximate it? The big breakthrough came a few years ago in a paper by Jerrum, Sinclair and Vigoda showing how to approximate the permanent if the entries are not negative.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/13/2003 2:49:21 PM

Powered by Blogger Pro

In 1994, the Handbook of Theoretical Computer Science was published as a two volume set each containing many survey articles that have for the most part stood the test of time. From the backcover: Volume A [Algorithms and Complexity] covers models of computation, complexity theory, data structure and efficient computation. Volume B [Formal Models and Semantics] presents material on automata and rewriting systems, foundations of programming languages, logics for program specification and verification and modeling of advanced information processing.

Over the years, Theory A and Theory B have come to represent the areas discussed in the corresponding volumes. In the US the term theoretical computer science covers areas mostly in Theory A. For example STOC and FOCS, the major US theory conferences, cover very little in Theory B. This is not to say Theory B is not done in this country; it is just labelled as logic or programming languages.

Outside the US there is a broader view of what is theory. The European ICALP conference covers both areas and has two submission tracks A and B that again correspond to Theory A and B.

Some countries, like Britain and France, focuses mostly on Theory B. Other countries, like the Netherlands and Germany have many groups in both areas.

Some Europeans are upset that their research is not considered theory by the Americans. Too bad.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/11/2003 1:47:55 PM

Powered by Blogger Pro

The general problem is PSPACE complete shown by Eric Baum and Gary Flake when they were at NEC. Tromp tells me that he has shown the problem is still PSPACE-complete when the cars are 2x1. Oddly enough the 1x1 case is the hardest to analyze and its complexity remains wide open.

Also check out Tromp's Rush Hour mazes.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/4/2003 4:37:10 AM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/25/2003 3:50:31 PM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/24/2003 2:03:30 PM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/21/2003 2:12:56 PM

Powered by Blogger Pro

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

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 Σ₂ remains the most interesting open question about this class.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/17/2003 11:05:32 AM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/16/2003 11:11:39 AM

Powered by Blogger Pro

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

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/14/2003 11:01:30 AM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/13/2003 10:53:05 AM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/11/2003 5:05:29 PM

Powered by Blogger Pro

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 the Church-Turing thesis fails to capture computation.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/5/2003 5:12:51 PM

Powered by Blogger Pro

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.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 2/3/2003 12:34:03 PM

Powered by Blogger Pro

Have a great week everyone and I will see you in February.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 1/24/2003 2:16:54 PM

Powered by Blogger Pro

Why am I mentioning this result here? The problem of testing whether a graph is perfect in polynomial-time remained open even after this theorem as neither characterization gives an obvious algorithm. I just saw the the abstract of a talk that Paul Seymour will give at the Institute of Advanced Study next week. There he claims he and Chudnovsky have found a polynomial-time algorithm for testing whether a graph is perfect. I cannot find more about the algorithm on the web and I will miss the talk at the institute. I will post more information about this exciting new development when I have more details.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 1/24/2003 11:25:07 AM

Powered by Blogger Pro

As an example, consider the square function, square(x)=x*x. Suppose we don't care about the name and just want to talk about the function in the abstract. The lambda calculus gives us the syntax for such discussions. We express the square function as

1. Every variable is a lambda term.
2. If M is a lambda term then (λx.M) is a lambda term.
3. If M and N are lambda terms then MN is a lambda term.

We use the notation M[x:=E] means replace every occurrence in the lambda term M of the free variable x by the lambda term E. There should not be any free variables in E that are bound in M as this could cause confusion.

There are two basic operations:
(renaming variables formally called α-conversion) λx.M to λy.M[x:=y]
(function evaluation formally called β-reduction) λx.M(E) to M[x:=E]

Church and Rossner have shown that if you have a complicated lambda-term it does not matter what order the β-reduction operations are applied.

What can you do with just these simple operations? You get the same power as Turing machines! It's instructive to see this connection and we'll go over the proof over several posts in the future.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 1/23/2003 11:31:08 AM

Powered by Blogger Pro

Each year for the past dozen years, I receive various papers by people I've never heard of claiming great results in computer science or mathematics. I started the Why Me? file to collect these various manuscripts. In those early ancient days I received papers by postal mail, now I always get them electronically. All of the papers have been incorrect ranging from subtle errors to papers that just don't understand the question. What motivates these people? A chance for glory I suppose.

Most of the papers I get are variants on the P versus NP question, though a surprising number claim to have counterexamples to Cantor's Theorem that there are more reals than integers. As one author put it, "Sure, Cantor's Theorem is true if you consider only integers with a finite number of digits." My favorite is one of the earliest letters I got from a person who believes he deserves the first Noble (sic) prize in mathematics. "We have conclusively shown that Einstein's c² in E=mc² is different than Pythagoras' c² in a²+b²=c²." And all this time I thought E=m(a²+b²).

I never spend more than a few seconds on any of these papers and I certainly never respond which is only asking for trouble. If there is any chance of it being correct, I can wait until someone else finds the bug.

Here is my suggestion to any of you who think you have the theorem of the century: Send it to a grad student with an opening line like "Because you are an expert in complexity...". They'll happily read your paper and tell you the errors of your ways. If by some fluke the result is correct the student will spread it around to the community and you'll get your fifteen minutes of fame.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 1/21/2003 12:08:09 PM

Powered by Blogger Pro

We will show that CNF-SAT is NP-complete. Let A be a language in NP accepted by a nondeterministic Turing machine M. Fix an input x. We will create a 3CNF formula φ that will be satisfiable if and only if there is a proper tableau for M and x.

Let m be the running time of M on x. m is bounded by a polynomial in |x| since A is in NP. m is also a bound on the size of the configurations of M(x).

We will create a set of Boolean variables to describe a tableau and a set of clauses that will all be true if and only if the tableau is proper. The variables are as follows.

• q_ij: true if conf_i is in state j.
• h_ik: true if the head in conf_i is at location k.
• t_ikr: true if the tape cell in location k of conf_i has element r.

1. Every configuration has exactly one state, head location and each tape cell has one element.
2. conf₀ is the initial configuration.
3. conf_m is accepting.
4. For each i≤m, conf_i+1 follows from conf_i in one step.

At this point none of the formula has been dependent on the machine M. Our last set of clauses will take care of this. Recall the program of a Turing machine is a mapping from current state and tape character under the head to a new state, a possibly new character under the head and a movement of the tape head one space right or left. A nondeterministic machine may allow for several of these possibilities. We add clauses to prevent the wrong operations.

Suppose that the following is NOT a legitimate transition of M: In state j and tape symbol r, will write s, move left and go to state v. We prevent this possibility with the following set of clauses (for all appropriate i and k).

What do we know about the National Security Agency? While they don't have the best American mathematicians, who typically go to universities, they have a large collection of very good mathematicians. While they are free to read the same papers I read, we hear about very little of their work. They must have some exciting work in algorithms and complexity I can only dream about. Perhaps they have an efficient factoring algorithm or a working quantum computer in their basement. Unlikely, but possible.

Occasionally I meet NSA scientists at conferences, particularly those meetings devoted to quantum computation. "The NSA is much more interested in quantum computing than quantum cryptography," one such scientist told me. This surprised me since quantum cryptography seems much more likely to have real-world applications than quantum computers, both in theory and in practice. "The real issue is how long our current codes will remain unbreakable. We need to know if our the information currently encrypted will remain safe for 20 or 50 years."

So is Enemy of the State realistic? "Not at all," a different NSA employee told me at a quantum workshop shortly after the movie came out. "We work in boring cubicles, not the sleek offices depicted in the movie." Offices?! What about the satellites that can track people on the ground in real time? "No comment."

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 1/15/2003 7:01:26 AM

Powered by Blogger Pro