[My Computational Complexity Web Log] 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 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
- For all x and y, x is in A if and only if p(x,y) is in A.
- p is 1-1 and |p(x,y)|>|x|+|y|.
- p is computable in polynomial-time.
- 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
- u is a reduction: For all x, x is in A if and only if u(x) is in B.
- u is 1-1 and onto.
- u and its inverse are both computable in polynomial time.
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.
Posted by Lance Fortnow to My Computational Complexity Web Log at 4/22/2003 9:41:40 AM
Powered by Blogger Pro
- A set A is paddable if there is a polytime computable function p:Σ*×Σ*→Σ* such that