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

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?

• I presume you're aware that it's possible no such function exists? What do you want to do in that case?
– D.W.
Jun 9, 2020 at 6:58
• We'd prefer that you ask one question per post. I suggest asking the question about computational complexity separately from the question about computability.
– D.W.
Jun 9, 2020 at 7:01
• The answer is the same for both, so I think this should count only as one question.
– Arno
Jun 9, 2020 at 9:46

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$$.
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.