The Berman-Hartmanis Isomorphism Conjecture

In 1976, Berman and Hartmanis considered whether all of the NP-complete problems might be the same. We says sets A and B are polynomial-time isomorphic if there exists a function f such that

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.

Conjecture (Berman-Hartmanis): Every pair of NP-complete sets are isomorphic.

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.

Is P versus NP undecidable?

Haipeng Guo asks "Is is possible that the P vs NP problem is undecidable? Is there any paper talking about this?"

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.

Foundations of Complexity Lesson 16: Ladner's Theorem

Previous Lesson | Next Lesson

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.

On Basketball and Politics

Some follow-up on earlier posts of this week.

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.

ICALP Papers Announced

The accepted papers for ICALP have been posted. As I mentioned last week, ICALP has two submission tracks that match the Theory A and Theory B split. The list of accepted papers though has both tracks intermingled. See if you can guess which papers are from track A and which papers are from track B.

Information Markets

Suppose you want to make a prediction on say who will win the Best Actress Award at Sunday's Oscars. You can visit various web sites, look at the predictions of so-called experts, look at polls, etc. Aggregating all of this information to make a single prediction seems quite difficult.

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

It's Not a Tree After All

On Sunday, I posted a link to the 2003 NCAA Division 1 Men's Basketball Championship Brackets which I called "America's Favorite Binary Tree". But in a strange twist the championship is not quite a tree this year.

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.

War and This Weblog

I was teaching my class right after the first Gulf war started in 1991 and wondering what to say. Sometimes I wish I were a history or government professor and could bring in current events into my lectures. But I taught computer science so I mumbled a few words acknowledging the conflict and went on to talk about NP-completeness or whatever I was teaching back then.

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.

March Madness

Check out America's Favorite Binary Tree.

Doing homework the hard way

In yesterday's post I linked to some lecture notes of Vigoda on Valiant's result. Those notes also cite a paper of Zankó. Now every paper has a story but this one is a little more interesting than most.

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.

Complexity Class of the Week: The Permanent

Previous CCW

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

Det(A)=Σ_σ(-1)^|σ| a_1σ(1)a_2σ(2)...a_nσ(n) where σ ranges over all permutations on n elements and |σ| is the number of 2-cycles one has to apply to σ to get back the identity.

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

Perm(A)=Σ_σ a_1σ(1)a_2σ(2)...a_nσ(n) Suppose G is a bipartite graph and let a_ij be 1 if there is an edge from the ith node on the left to the jth node on the right and 0 otherwise. Then Perm(A) is the number of perfect matchings in G.

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.

Theory A and Theory B

Four speakers are chosen for the NVTI Theory Day along two axis: In and out of the Netherlands, and Theory A and Theory B. For example I was the non-Dutch Theory A speaker. But what is Theory A and B?

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.

Talk Posted

I posted the slides of my talk, "Church, Kolmogorov and von Neumann: Their Legacy Lives in Complexity" that I presented at the Dutch Theory Day last week, for those that are interested.

Rush Hour

John Tromp at CWI has been telling me about some work he is doing on the Rush Hour problem. Rush Hour is a puzzle where you have to remove a car stuck in gridlock. A nice description of the problem is presented in a Science News article.

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.

Cardinality Theorem for Regular Languages?

Till Tantau told me an interesting open question at STACS. Kummer proved the following Cardinality Theorem for the recursive sets: Fix a constant k and set A. If there is a recursive function f such that for all x₁,...,x_k, f(x₁,...,x_k) is a number between 0 and k that is not |{x₁,...,x_k}∩A| then A is recursive. The same is not true for polynomial time but is open for regular languages. Details and some partial results in Tantau's paper.