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?

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

StackExchange Computer Science Q#126947, answer score: 7