Day 7

The Cantor-Bernstein Theorem states that for any two arbitrary sets A and B if there are 1-1 functions from A to B and B to A then there is a 1-1 and onto function from A to B. How does this carry into complexity?

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

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

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

1. f is computable in polynomial time
2. The inverse of f is computable in polynomial time
3. f is 1-1
4. f is length-increasing, i.e., |f(x)| > |x| for all strings x.

We define A to be paddable if there is a function h:Σ^*×Σ^*→Σ^*

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

We showed (see Berman-Hartmanis) that

1. Every A in NP reduces to Satisfiability via a 1-1 length-increasing reduction.
2. If B reduces to a paddable set A then there is a reduction from B to A that is length-increasing and invertible. 
3. 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.