Computational Complexity

Friday, March 28, 2003

 
The Berman-Hartmanis Isomorphism Conjecture

Posted by Lance

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.

9:25 AM # 1 comments

1.  Derrick Coetzee says:  
   
   This post left open the question of why researchers believe the isomorphism conjecture is false. The most compelling evidence that I'm aware of was presented in "The isomorphism conjecture fails relative to a random oracle" by Kurtz, Mahaney, and Royer, which asserts what its title says. Moreover they make the claim that although some results hold in the unrelativized case but not for a random oracle (like IP=PSPACE), they believe that the isomorphism conjecture does fail in the unrelativized case. Here is their argument:
   
   "Both counterexamples [to the random oracle conjecture] have a common flavor. Imagine that there are exponentially many boxes, one of which contains a prize. If the prize is placed at random, then a computational agent that can only examine polynomially many boxes has essentially no chance of finding the prize, no matter how powerful he may be. If, on the other hand, the prize is placed only pseudorandomly, then a sufficiently powerful computational agent will find it every time. Both counterexamples rely on finding computational agents (P^SAT or IP) that are strong enough to defeat any polynomial time pseudorandom prize-hiding strategy; but these agents must themselves be defeated when presented with a truly random prize-hiding strategy. [...] In our case, the computational agents we will consider will be in P, and so, in some sense, we end up relying on the fact that P^R isn't powerful enough to search R. But now we're back to the observation upon which the random oracle conjecture was based: there seem to be good pseudorandom languages in P, and we only need them to be good enough to defeat P, not P^SAT or IP. We believe that such pseudorandom languages exist, and that therefore the unrelativized isomorphism conjecture fails."
   

   7:50 PM, October 03, 2007

Comment Feeds: This Post All