Two sets of strings A and B are polynomial-time isomorphic if there is a function f:Σ

^{*}→Σ

^{*}

- f is computable in polynomial time
- The inverse of f is computable in polynomial time
- f reduces A to B (x in A iff f(x) in B)
- f is 1-1
- f is onto

We say f is a length-increasing invertible reduction if there is a f:Σ

^{*}→Σ^{*}- f is computable in polynomial time
- The inverse of f is computable in polynomial time
- f is 1-1
- f is length-increasing, i.e., |f(x)| > |x| for all strings x.

^{*}×Σ

^{*}→Σ

^{*}

- h is computable in polynomial time
- For all x,y, x is in A iff h(x,y) is in A
- For all y, |h(x,y)| > |y|
- For all x, y and y' with y≠y', h(x,y)≠h(x,y')
- There is a polynomial-time computable function g s.t. for all x,y, g(h(x,y))=y

- Every A in NP reduces to Satisfiability via a 1-1 length-increasing reduction.
- If B reduces to a paddable set A then there is a reduction from B to A that is length-increasing and invertible.
- If A and B reduce to each other via length-increasing invertible reductions then they are isomorphic.

Essentially all the commonly known NP-complete problems are paddable and thus isomorphic to Satisfiability and each other.