Given A to C, and B to C with known complexities, what can be said about A to B?

Question

Say I have two sets of values $A$ and $B$ and for each set I have a computable function from that set to a third set $C$. Now suppose that I want to construct a function from $A$ to $B$, such that if I compose that function with the $B$ to $C$ function mentioned above I get a function that produces the same results as the $A$ to $C$ function mentioned above.

If I know the time-complexity of the two functions that return elements of $C$, does that allow me to say anything about a function from $A$ to $B$ with the specified property? For example can any bounds be placed on the computational complexity of such a function? Can we even say whether such a function is computable or not?

Answer 1

We can have sets $A, B, C$ with linear-time computable maps $f : A \to C$ and $g : B \to C$ such that there exists a map $h : A \to B$ with $f = g \circ h$, but the needed time complexity/Turing degree for $h$ is as high as you want.

Proof: Pick a map $H : \Sigma^* \to \Sigma^*$ which is hard in whatever sense you have chosen. Now let $A = C = \Sigma^*$, and $B = \{\langle w, H(w)\rangle \mid w \in \Sigma^*\}$. Let $f = \mathrm{id}$ and $g = \pi_1$, i.e. $g(\langle w,u\rangle) = w$. Now $A,B,C$ and $f,g$ meet the criteria of the claim, and the only map $h$ that works is $h(w) = \langle w, H(w)\rangle$, which is essentially as hard as $H$.

Answer 2

You're asking two questions, one about computability and one about computational complexity. The usual rule is to ask one question per post. I'll answer the second question. No, under standard conjectures, the computational complexity could be quite bad. Suppose $f:A \to C$ is given by $f(x) = \alpha^x \bmod p$ and $g:B \to C$ is given by $g(x) = \beta^x \bmod p$, where $p$ is a large prime number. Then you can compute $f,g$ in polynomial time; but finding a map $A \to B$ is as hard as computing the discrete log of $\beta$ to base $\alpha$, which is conjectured to be hard.

Answer 3

Public key cryptography is based on the idea that the complexity can be made very high.

Let A be the set of public keys, and B be the set of private keys, and C the set of results of encrypting some fixed plain text. Both public and private key allow you to calculate the encrypted text quite easily. But you are asking if given a public key, you can calculate a private key giving the same encrypted message. Since the plain text must be the same to get the same encrypted message, this would immediately give you the private key to any public key.