First some definitions:

- A set A is paddable if there is a polytime computable function
p:Σ
^{*}×Σ^{*}→Σ^{*}such that- 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
such that
- 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)=y then let u(x)=r(x) otherwise let u(x)=y.

## No comments:

## Post a Comment