Loading ...
Sorry, an error occurred while loading the content.

[My Computational Complexity Web Log] The Berman Hartmanis Isomorphism Conjecture

Expand Messages
  • Lance Fortnow
    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
    Message 1 of 1 , Mar 28, 2003
    • 0 Attachment
      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.

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

      Powered by Blogger Pro

    Your message has been successfully submitted and would be delivered to recipients shortly.