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

[My Computational Complexity Web Log] Paddable NP-Complete Sets are Isomorphic

Expand Messages
  • Lance Fortnow
    By request, here is a sketch of the proof of the Berman-Hartmanis 1978 result that all paddable NP-complete sets are isomorphic. The proof is builds on an old
    Message 1 of 1 , Apr 22, 2003
    • 0 Attachment
      By request, here is a sketch of the proof of the Berman-Hartmanis 1978 result that all paddable NP-complete sets are isomorphic. The proof is builds on an old result of Myhill that all r.e.-complete sets are recursively isomorphic. Since nearly all natural NP-complete sets are paddable then they are also isomorphic.

      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.
      Suppose A and B are paddable NP-complete sets. Let f reduce A to B and g reduce B to A. Let p be a padding function for A and q a padding function for B. Let r(x)=q(f(x),x) and s(y)=p(g(y),y). The function r is a 1-1 length-increasing efficiently-invertible-on-its-range reduction from A to B and s is the same from B to A.

      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.
      Since r and s are length-increasing, the depth of the recursion is at most the length of x so u is computable in polynomial time. I'll leave it to the reader to verify that u is an isomorphism.

      --
      Posted by Lance Fortnow to My Computational Complexity Web Log at 4/22/2003 9:41:40 AM

      Powered by Blogger Pro

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