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

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

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

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

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

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

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

Short Answer: Until we have a proof that P≠NP or a proof that P=NP, we cannot rule out the possibility that the P versus NP question is not provable in one of the standard logical theories. However, I firmly believe there exists a proof that P≠NP. To think that the question is not provable just because we are not smart enough to prove it is a cop-out.

You'll have to be patient for the long answer. The October 2003 BEATCS Complexity Column will be devoted to this topic.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 3/27/2003 7:23:22 AM

Powered by Blogger Pro

1. x is in A if and only if f(x) is in B (f reduces A to B),
2. f is a bijection, i.e., f is 1-1 and onto,
3. f is polynomial-time computable, and
4. f^-1 is polynomial-time computable.

The Isomorphic Relation between sets is an equivalence relation. The Berman-Hartmanis conjecture is equivalent to saying that every NP-complete set is isomorphic to SAT.

The conjecture is still open though it has generated a considerable amount of research in computational complexity. But for now let me just explain why this question is interesting.

Berman and Hartmanis showed that all of the natural NP-complete sets at the time, for example all of the problems listed in Garey & Johnson, are isomorphic. They established this fact by proving that every paddable NP-complete set is isomorphic to SAT. A set A is paddable if there is a polynomial-time computable length-increasing function g such that for all strings x and y, x is in A if and only if g(x,y) is in A.

Most NP-complete sets are easily seen to be paddable. Consider the clique problem. Given a graph G and a string y, we can create a new graph H that encodes y by adding disjoint edges to G while keeping the clique size of H the same as the clique size of G.

The isomorphism conjecture implies P≠NP, since if P=NP then there would be finite NP-complete sets which cannot not be isomorphic to the infinite set SAT. There was a time when Hartmanis was pushing on the idea of using the conjecture to prove P≠NP but most complexity theorists now believe the isomorphism conjecture is false.

More on the isomorphism conjecture in future posts.

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

Powered by Blogger Pro

So it seems that the Shimura Taniyama conjecture is not true after all. The experts think that it can still be salvaged, by extending the concept of automorphic representation, and introducing a notion of "anomalous curves" that would still give rise to a "quasi-automorphic representation".

This is an email I received indirectly from the late Gian-Carlo Rota dated April 2, 1994. The historical context: In June of 1993, Andrew Wiles announced that he had proven Fermat's Last Theorem but later that year a subtle bug was bound which was not fixed until September of '94.

So in April of 1994 we didn't know whether Wiles' proof was valid and given the date was April 2 and how well the email was written, many mathematicians believed this message. But of course it was all an elaborate April Fools joke.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/1/2003 8:33:49 AM

Powered by Blogger Pro

Zorn, grandson of the mathematician Max Zorn, wrote this column that put Wiles' proof of Fermat in a context of the Chicago Bulls basketball team winning a recent championship. I was in the CS department at the University of Chicago during that time and the parallels hit home for me: "Andrew Wiles" = "Michael Jordan", "Yoichi Miyaoka" = "Charles Barkley", "Rie-Peat" = "Three-peat", "Doing set theory in a New Jersey library" = "Gambling in Atlantic City", etc. You get the picture.

Or maybe you had to be there. After this article made the email rounds, one European professor asked me if there really were graduate students rioting in Chicago. Go figure.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/7/2003 4:50:49 PM

Powered by Blogger Pro

Wegner and Goldin's main argument is summed up towards the end of the article. "In the last two decades, computing technology has shifted from mainframes and microstations to networks and wireless devices, with the corresponding shift in applications from number crunching and data processing to embedded systems and graphical user interfaces. We believe it is no longer premature to encompass interaction as part of computation. A paradigm shift is necessary in our notion of computational problem solving, so it can provide a complete model for the services of today's computing systems and software agents."

In here they have a good point. The area of human-computer interaction is sometimes more art than science. But while the basic model of the Turing machine is a sequential device, theoretical computer scientists have come up with variations that capture networks and other aspects of interaction, some of which are described in the Wegner-Goldin article. And all of these new models can be simulated by Turing machines. The Turing machine remains supreme as the model that captures all computation.

Far more troubling is the following: "Gödel had shown in 1931 that logic cannot model mathematics and Turing showed that neither logic nor algorithms can completely model computing and human thought." This is a complete misreading of Gödel and Turing. Not every mathematical statement has a logical proof, but logic does capture everything we can prove in mathematics, which is really what matters. Likewise, Turing machines captures everything we can compute. And what we can compute is what computer science is all about.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/8/2003 11:02:59 AM

Powered by Blogger Pro

The major negative is that I have lost all of the old comments. I apologize for this. Please feel free to repost your old comments or add new ones.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/8/2003 1:21:01 PM

Powered by Blogger Pro

I guess Alexander Razborov turned to the study of Propositional Proof Systems because he wanted to prove that "proving SAT is not in P/poly" is hard in a formal sense. What is his opinion about undecidability? (Of course I know I should ask him, but he doesn't have such a nice message board. :))

I passed the question to Razborov and here is his response.

Dear Daniel, First, I understand that "undecidability" in your question should read "unprovability" (or, otherwise, I misunderstood it). And the answer to it very much depends on the strength of the formal theory we are interested in. For classical theories like Peano Arithmetic or Set Theory I do not have enough intuition (not even to mention evidence) to articulate any opinion. The only thing which seems quite sure to me is that such an independence result, if true, would not be much easier to prove than the original P vs. NP question itself... If we, however, descend in the logical hierarchy to weaker theories capturing poly-time computations (commonly known as Bounded Arithmetic), the answer becomes quite different. I do conjecture that "SAT is not in P/poly" is independent from these theories. Moreover, I believe that if we allow ourselves a standard cryptographic assumption (FACTORING is hard, for definiteness) this question might be more attainable with currently know! n techniques than those discussed above. Further, I expect that if we ever manage to prove such an independence result, its proof would be very illuminating in approaching the question "what's next and what are we missing?" (cf. Natural Proofs). Finally, let me mention that the introduction to the paper "Pseudorandom Generators Hard for k-DNF Resolution and Polynomial Calculus Resolution" (available from my Web site) contains an expanded version of some of these views. Alexander.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/8/2003 5:22:01 PM

Powered by Blogger Pro

Jim Holt reviews George Johnson's A Shortcut Through Time: The Path to a Quantum Computer. I haven't seen Johnson's book yet but the more I read about the more I recommend it to laypeople who are interested in quantum computers. It really seems like he gives an understanding of quantum computation without overly hyping the topic.

There is also an article from the circuits section on new work on at the Weizmann Institute on DNA computers. As typical with articles on DNA computing in the New York TImes, you should read the end of the article first. That way you get the reality before the hype.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/12/2003 7:28:14 AM

Powered by Blogger Pro

1. Open.
2. Doable.
3. Interesting.

I generally give the advice that my advisor, Michael Sipser, gave to me. Pick up a proceedings of a recent conference in your area and read through the abstracts of papers until you find one that interests you. The "interests you" part is important, for without it you won't have the motivation to study further.

Read the paper thoroughly. Read related papers. If you lose interest, start the process all over again.

Once you've read several papers in an area that interests you talk about it with your advisor and your fellow graduate students. Some of these papers might list open questions and you could work on those. You might say, "Karp listed this as an open question, and if Karp can't solve it why should I be able to?" Karp is a very smart but also very busy person. It is unlikely he spent more than an hour thinking hard about these questions. As a graduate student you can spend much more time focusing on these problems and could easily make more progress than someone like Karp could.

Even better is to formulate your own problems. Perhaps there is an interesting variation in a model that the original paper, for whatever reason, did not cover. Perhaps you can find connections between two papers that no one had noticed before. These are great problems to work on: As you are breaking new ground, theorems can start flowing like water. Just remember not to have too much weirdness in your questions; keep the research interesting.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/14/2003 10:48:03 AM

Powered by Blogger Pro

Rumors are flying that theorists Ron Rivest, Adi Shami and Len Adleman won the Turing Award for their work on the RSA cryptosystem. The Turing Award is the highest honor in computer science, the closest we have to a Nobel prize.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/15/2003 6:59:49 AM

Powered by Blogger Pro

Unfortunately outside of computer science and particularly outside academics the Turing award is not so well known or respected. In 1987, I was a graduate student visiting my old fraternity at Cornell, Anne Marie Hopcroft came in. Anne Marie was dating one of the fraternity brothers at the time. "My father won the Turing Award! My father won the Turing Award!", she exclaimed. Nobody, besides myself, seemed the least bit interested. She and I tried to explain the importance of the award but to no avail. Had her father won the Nobel prize, you could be sure the reaction would have been different.

The 1997 movie Good Will Hunting gave great publicity for mathematics much by explaining the importance of the Fields Medal to the masses. What can we do to make the Turing Award better known?

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/18/2003 7:22:02 AM

Powered by Blogger Pro

First some definitions:

• A set A is paddable if there is a polytime computable function p:Σ^*×Σ^*→Σ^* such that
  1. For all x and y, x is in A if and only if p(x,y) is in A.
  2. p is 1-1 and |p(x,y)|>|x|+|y|.
  3. p is computable in polynomial-time.
  4. p is invertible on its range in polynomial-time.
• Sets A and B are isomorphic if there is a reduction u from A to B such that
  1. u is a reduction: For all x, x is in A if and only if u(x) is in B.
  2. u is 1-1 and onto.
  3. u and its inverse are both computable in polynomial time.

Now we can define our isomorphism u(x) from A to B.

• If x is not in the range of s then let u(x)=r(x).
• If x is in the range of s, let y be such that s(y)=x.
• If y is not in the range of r then let u(x)=y.
• If y is in the range of r, let z be such that r(z)=y.
• Recursively compute u(z).
• If |u(z)|>|z| then let u(x)=r(x) otherwise let u(x)=y.

Two new complexity classes developed independently for two different purposes with eerily similar definitions. Let's take a look.

Böhler, Glaßer and Meister present a new class SBP that can be defined as follows. A language L is in SBP if there is a #P function f and an FP function g such that for all x,

1. if x is in L then f(x)>g(x), and
2. if x is not in L then 0≤f(x)<g(x)/2.

In both classes the "2" in the definition can be replaced by 2^|x|k for any fixed k.

SBP sits between MA and AM, a rare natural class between these two. SBP is also contained in BPP_path but there is a relativized world where it is not contained in Σ₂, giving a relativized answer to the open question in my CCW on BPP_path. SBP is closed under union but whether it is closed under intersection remains open even in relativized worlds.

QMA, the quantum version of MA, is contained in A₀PP, which itself is contained in PP. If A₀PP = PP then PH is in PP. He claims this gives evidence that QMA is not PP but given strong pseudorandom function, PH is in PP. But co-NP is probably not in QMA which is evidence enough for me that QMA is not equal to PP.

To prove his later result, Vyalyi notes that P^#P[1] is in SPP^C₌P and he shows that SPP^A₀PP is contained in PP and his result follows since C₌P is in PP and by Toda's Theorem PH is in P^#P[1].

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/23/2003 7:40:25 AM

Powered by Blogger Pro

To celebrate the centennial, I'm back in Dagstuhl for a workshop on Kolmogorov complexity after a brief stop in Heidelberg. Most of the best researchers in the area are here including many Russians. It should be an exciting week all around and during the week I will post some of the interesting work that I hear about.

For a background on Kolmogorov complexity, here are some lecture notes from a short course I gave. For an in-depth study, I cannot recommend enough the Kolmogorov Complexity book of Li and Vitanyi.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/27/2003 10:16:52 AM

Powered by Blogger Pro

At this Dagstuhl workshop there are many talk on a number of variations of Kolmogorov complexity. John Tromp had a nice presentation on the basic notion. He showed, among other things, that for any x you can find a constant length y such that C(xy)>C(x). This seems obvious but it is pretty tricky tor prove. Tromp's proof works by defining a new C-based measure on strings and using that to show that any string x has a small number of programs generating x that have length close to C(x) and using that fact to get his result. He doesn't have a write-up yet, but I'll keep a lookout for it.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/29/2003 4:13:17 AM

Powered by Blogger Pro

R is co-r.e. as one can enumerate small programs to generate the strings x such that C(x)<|x|. One can also reduce the halting problem to R: Suppose we want to know whether a program p halts on blank tape. Let n=|p|. Let t be the number of steps to enumerate all of the strings in R of length 2n. We know when we have enumerated them all by using R. Then if p halts it will halt within t steps. Otherwise let s>t be the number of steps p needs to halt. We can run the enumeration of strings in R of length 2n for s steps. Let x be the lexicographically least string of length 2n not enumerated. We have C(x)≤|p|+O(1) since we need only p to describe this process. But since |p|<2n=|x| this contradicts the fact that we had enumerated all the nonrandom strings.

In this workshop Eric Allender talked about his work with various colleagues looking at what one can get with polynomial-time reductions to random strings. The reduction time above is not bounded by any recursive function. For example they can show any language in PSPACE polynomial-time reduces to R and any language in EXP reduces to R via polynomial-size circuits, as well as many results on different notions of random strings. They use various complexity tools like pseudorandom generators and interactive proof systems in their proofs.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/30/2003 11:34:28 AM

Powered by Blogger Pro

Let me finish off this centennial week with a story of Kolmogorov that I have heard from different sources so some variation of this story is likely true. Kolmogorov initially wanted to be an historian. He looked at the question as to whether taxes in Russia in the middle-ages were collected at the house level or at the village level. He analyzed tax data and showed that that data had a much simpler description if taxes were collected at the village level. (You can see the seeds of Kolmogorov complexity here). He presented these results to the history faculty to great applause. Asking them whether he could publish such a paper he was told, "You only have one proof. You cannot publish in a history journal without at least two more proofs of your hypothesis." And so Kolmogorov left history for a field where one proof suffices.

--
Posted by Lance Fortnow to My Computational Complexity Web Log at 5/2/2003 12:40:55 AM

Powered by Blogger Pro