Given functions $h,k:\Bbb R\to \Bbb R$, is it possible to determine whether $f,g:\Bbb R\to\Bbb R$ exist so that $g\circ f=h$ and $f\circ g=k$? Let's say I have two functions $h,k:\Bbb R\to \Bbb R$.  I want to find $f,g:\Bbb R\to \Bbb R$ such that $g\circ f=h$ and $f\circ g=k$.  I know that $f,g$ might not exist (for example, Functional equation involving composition and exponents).  Do we know at least a condition for $h,k$ such that $f,g$ exist?
Which condition guarantees the uniqueness of $f,g$ (provided that they exist)?  Note that there are $h,k$ such that $f,g$ are not unique. For example, $h=k=0$, where $f=0$ works and $g$ is any function s.t. $g(0)=0$.  Or when $h=k$ is the identity function, and we take $f$ to be any bijection and $g=f^{-1}$.
At the very least, what do we know about this problem when $h,k$ are polynomial functions?  Is there a simple test that tells us there are polynomials $f,g$ that satisfy the conditions for a given pair of polynomials $h,k$?  Again, what about the uniqueness of polynomial solutions?

If the general problem is too hard, I am most interested in this specific problem. I want to find $f,g:\Bbb R\to\Bbb R$ such that
$$g\circ f(x)=x^3+1$$
and
$$f\circ g(x)=x^3+3x^2+3x+2.$$
Clearly $f,g$ are bijective functions if they exist.  So, can we determine the value of $g\circ f^{-1}(-7)$?
I found $f,g$ that almost work.  When $f(x)=x^3$ and $g(x)=x+1$, we have $g\circ f(x)=x^3+1$ but $f\circ g(x)=x^3+3x^2+3x+1$.  Unfortunately they don't quite work.  I know also that there are no polynomial functions $f,g$ that work.
Note that
$$f(x^3+1)=f(x)^3+3f(x)^2+3f(x)+2$$
and
$$g(x^3+3x^2+3x+2)=g(x)^3+1.$$
$\therefore$ if $a,b$ are the unique real numbers such that $a^3+1=a$ and $b^3+3b^2+3b+2=b$, we see that $f(a)=b$ and $g(b)=a$.  These are the only values of $f$ and $g$ that I know.  But I can also see that
$$ f^{-1}(-7)=g(-3)$$
if that helps.
Let $h(x)=x^3+1$ and $k(x)=x^3+3x^2+3x+2$.  Due to $f\circ g(x)$ and $g\circ f(x)$ are given; find $f$ and $g$, if $f=f_0$ and $g=g_0$ satisfy the conditions, then $f=f_0\circ \phi$ and $g=\phi^{-1}\circ g_0$ form a solution for any bijection $\phi:\Bbb R\to\Bbb R$ such that $h\circ \phi=\phi\circ h$.  Because any iteration of $h$ commutes with $h$, we can see that there are infinitely many $f$ and $g$, if $f_0,g_0$ exist.  How do I see whether $f_0,g_0$ exist?
 A: This is an addendum to the very brilliant analysis already given by orangeskid. In light of their analysis, I'll provide some easy facts about topological conjugation over the reals.

Claim 1: If $f:\mathbf{R}\to\mathbf{R}$ is strictly increasing, continuous, unbounded above and below, and such that $f(0)>0$, then there is a strictly increasing and continuous $\varphi:\mathbf{R}\to\mathbf{R}$ such that $\varphi(0)=0$ and $f\circ\varphi(x)=\varphi(x+1)$. Moreover if $f(x)>x$ for all $x\in\mathbf{R}$, then $\varphi$ is also unbounded above and below.
Proof: Since we know $f(0)>0$, let $\varphi(a)=af(0)$ for all $a\in[0,1)$. We will define the rest of $\varphi$ by extending in the obvious fasion: $\varphi(x)=f^{(\lfloor x\rfloor)}\circ\varphi\left(x-\lfloor x\rfloor\right)$, where $f^{(-)}$ denotes functional iteration, as $f$ is bijective. Clearly the next thing to do is to check that this fits the requirements:

*

*We forced $f\circ\varphi(x)=\varphi(x+1)$ by contsruction, so that is done.


*To check continuity, note that $f^{(\lfloor x\rfloor)}$ is always continuous, so by functional composition $\varphi$ is continuous over $\mathbf{R}\smallsetminus\mathbf{Z}$. To check continuity on $\mathbf{Z}$, it suffices to check continuity as $x\to 1^-$. For this note that
$$\varphi(1)=f\circ\varphi(0)=f(0)=\lim_{x\to 1^-}\varphi(x)$$


*To see $\varphi$ is strictly increasing, note that $f^{(\lfloor x\rfloor)}$ is strictly increasing by assumption and that $\varphi$ is strictly increasing over $[0,1)$, so we get $\varphi$ is strictly increasing over all intervals $[z,z+1)$ where $z\in\mathbf{Z}$. However $\varphi$ is continuous, and so it is strictly increasing over $\mathbf{R}$.
Now to check the "moreover" part.

*

*If $\varphi$ is not unbounded, then by monotone convergence, there is a bound $M=\lim_{x\to A}\varphi(x)$ where $A\in\pm\infty$. However, as $f$ is continuous,
$$f(M)=f\left(\lim_{x\to A}\varphi(x)\right)=\lim_{x\to A}f(\varphi(x))=\lim_{x\to A}\varphi(x+1)=M$$
This contradicts that $f(x)>x$ for all $x\in\mathbf{R}$.


Claim 2: If $f:[0,\infty)\to[0,\infty)$ is strictly increasing and continuous, such that $f(0)=0$ and $f(x)>x$ for all $x>0$, then there is a strictly increasing, continuous, and unbounded $\varphi:[0,\infty)\to[0,\infty)$ such that $\varphi(0)=0$ and $f\circ\varphi(x)=\varphi(2x)$.
Proof: Let $g:\mathbf{R}\to\mathbf{R}$ be given by $g(x)=\log_2 f(2^x)$. By Claim 1, there is some $\psi:\mathbf{R}\to\mathbf{R}$ that is strictly increasing, continuous, unbounded above and below, and such that $g\circ\psi(x)=\psi(x+1)$. Then let $\varphi(x)=2^{\psi(\log_2 x)}$, so we see that
$$\varphi(2x)=2^{\psi(1+\log_2 x)}=2^{g\circ\psi(\log_2 x)}=f(2^{\psi(\log_2 x)})=f\circ\varphi(x)$$

Claim 3: If $f:\mathbf{R}\to\mathbf{R}$ is strictly increasing, continuous, and has exactly one unstable fixed point $c$, that is, $f(x)>x$ for all $x>c$ and $f(x)<x$ for all $x<c$, then there is an increasing homeomorphism $\varphi:\mathbf{R}\to\mathbf{R}$ such that $\varphi^{-1}\circ f\circ \varphi(x)=2x$.
Proof: Let $g:\mathbf{R}\to\mathbf{R}$ be given by $g(x)=f(x+c)-c$, thus $g$ shares all properties with $f$ except $0$ is the fixed point of $g$. By Claim 2, there are increasing homeomorphisms $\varphi_{\pm}:[0,\infty)\to[0,\infty)$ such that $\varphi_{\pm}(0)=0$, and moreover both $\varphi_+^{-1}\circ g\circ\varphi_+(x)=2x$ and $\varphi_-^{-1}(-g(-\varphi_-(x)))=2x$. Let $\psi:\mathbf{R}\to\mathbf{R}$ be given by
$$\psi(x)=\begin{cases}
\varphi_+(x)&\text{if }x\ge 0\\
-\varphi_-(-x)&\text{if }x<0
\end{cases}$$
Then it is not hard to see that $\psi$ is an increasing homeomorphism such that $\psi^{-1}\circ g\circ\psi(x)=2x$. Finally let $\varphi:\mathbf{R}\to\mathbf{R}$ be given by $\varphi(x)=\psi(x)+c$, so then
$$2x=\varphi^{-1}(\psi(2x)+c)=\varphi^{-1}(g\circ\psi(x)+c)=\varphi^{-1}\circ f\circ\varphi(x)$$

As a corollary, note that both $x^3+1$ and $x^3+2$ satisfies Claim 3, so both are conjugate to $2x$.
Also note that it is completely possible to modify the proof such that both $x^3+1$ and $x^3+2$ are conjugate to $2x$ via a homeomorphism that is smooth on all of $\mathbf{R}$ except at the fixed point.
This is unavoidable:

Added Claim 4: Consider the two linear functions $f(x)=2x$ and $g(x)=4x$. Let $\varphi:\mathbf{R}\to\mathbf{R}$ be any homeomorphism such that $\varphi\circ f=g\circ\varphi$. Then $\varphi$ cannot be continuously twice differentiable at $0$.
Proof: Assuming not, then by Taylor's theorem we have
$$\varphi(x)=ax+bx^2+h(x)\cdot x^2$$
where $h$ is continuous at $h(0)=0$. Then by expanding on $\varphi\circ f=g\circ\varphi$, we eventually get
$$h(2x)-h(x)=\frac{a}{2x}$$
Taking the limit $x\to 0$ on both sides, we see that $a=0$, and $h(2x)=h(x)$. However the continuity of $h$ at $0$ implies that $h$ is identically $0$, meaning that $\varphi(x)=bx^2$, and $\varphi$ cannot be a homeomorphism.
A: If $h= g\circ f$ and $k= f\circ g$, one of the $h,k$ is surjective, and the other injective, then $f$, $g$, $h$, $k$ are all bijective and
$$k = f\circ h \circ f^{-1}$$,
that is $h$, $k$ are conjugate. Conversely, if $h$, $k$ are conjugate, then you can find $f$, and then $g$. Now, the conjugation is an equivalence relation.
Now in our example $h(x) = x^3+1$, $k(x) = (x+1)^3 + 1$, so $k(x-1) + 1 = x^3+2$, a conjugate of $k$. So now we want to see whether $h_1(x) = x^3+1$ and $h_2(x) =x^3+2$ are conjugate. Note that both have a unique fixed point $\xi_1$, $\xi_2$, and for $x> \xi_i$ we have $h_i^{n}(x) \to \infty$ as $n\to \infty$, $h_i^{n}(x) \to \xi_i$, as $n\to -\infty$, while for $x< \xi_i$, we have $h_i^{n}(x) \to -\infty$ as $n\to \infty$, $h_i^{n}(x) \to \xi_i$, as $n\to -\infty$. Therefore, all the orbits of $h_i$ -except the one containing the fixed point- are infinite. So there exists a bijection $\phi\colon \mathbb{R}\to \mathbb{R}$ such that $h_2= \phi\circ h_1\circ \phi^{-1}$.  It is clearly not unique, so a nice $\phi$ would be desired. Note that $\phi$ takes the fixed point of $h_1$ to the fixed point of $h_2$.
It appears that both $h_1$, $h_2$ behave like the map $x\to 2 x$. Are they topologically conjugate to it?  Note that $l(x) = 2x$ is part of a $1$-parameter group of diffeomorphism of $\mathbb{R}$, $(t,x)\mapsto 2^{t}\cdot x$. If $h_1$, $h_2$ are conjugate to $l$, then they are also each part of a $1$-parameter group of homeomorphisms of $\mathbb{R}$. In particular, there exists $\psi$ a homeomorphism of $\mathbb{R}$ such that $\psi\circ \psi(x) = x^3+1$.  What would be such a homeomorphism?
$\bf{Added:}$ The case where both $k$, $k$ are bijections is simpler, it reduces to the question of when two maps are conjugate under a bijection.  They are if and only if the "graph" of the maps are isomorphic, where the graph consists of  vertices $x$, and edges $(x, h(x))$.  For bijections, their cycle structure has to be the same.
Consider for instance the maps $x\mapsto 2 x$, and $x\mapsto 4 x$. They are conjugate under the bijection $x\mapsto x^{2_+}\colon = x^2 \operatorname{sign} x$.  The maps $x\mapsto 2x$, and $x\mapsto 3x$ are conjugate under the map $x\mapsto x^{\log_2 3_+}$.
