Tuesday, April 22, 2003

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.

No comments:

Post a Comment