Paddable NP-Complete Sets are Isomorphic

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 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)=y 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.