Given any function $g(x): \mathbb{R} \rightarrow \mathbb{R}$, find a function $f(x)$ such that $f(f(x)) = g(x)$. This is a problem I was casually discussing with friends:

Given any function $g(x): \mathbb{R} \rightarrow \mathbb{R}$, find a
  function $f(x): \mathbb{R} \rightarrow \mathbb{R}$ such that $f(f(x)) = g(x)$.

Is it possible to find a solution for $f(x)$ or prove that there isn't a solution for $f(x)$ such that $f(f(x)) = g(x)$ for any given $g(x)$? 
For example, if $g(x) = x + 2$, then $f(x)$ could easily be $f(x) = x + 1$. But if $g(x) = x^2 - 1$, then it's not clear to see what $f$ can satisfy such solution. 
What approach might be promising? My first gut reaction would be some analytical method but can't think of a way still...Discussions are welcomed! 
 A: You are looking for the functional square root of $g(x)$. In most cases it does exist, but the solutions are mind-bogglingly complicated. See the Wikipedia article for more information.
A: This is not intended to be a full answer, more like a thought experiment that is too long for a comment.
As @ParclyTaxel mentioned, functional square roots abound, but sometimes they are very difficult to find. Let me expand on this point via a simple example.
Consider the function $g:\mathbb C\to\mathbb C$ defined on the whole complex plane as $g(x)\equiv -x$ for each $x\in\mathbb C$. It is very easy to find a function $f:\mathbb C\to\mathbb C$ such that $f\circ f=g$; define $f(x)\equiv\mathsf ix$ for each $x\in\mathbb C$.
However, what if $g:\mathbb R\to\mathbb R$, still defined as $g(x)\equiv -x$ for $x\in\mathbb R$, is restricted to the real line? A solution to the functional-square-root problem still exists, but the answer is way less obvious in this case.
To exhibit one such solution, first note that the intervals $(0,1)$ and $[1,\infty)$ have the same cardinality, so that there exists a bijection $h:(0,1)\to[1,\infty)$ between them. Denote the inverse as $h^{-1}:[1,\infty)\to(0,1)$. Define $f:\mathbb R\to\mathbb R$ as follows:
\begin{align*}
f(x)\equiv\begin{cases}h^{-1}(-x)&\text{if $x\in(-\infty,-1]$},\\-h(-x)&\text{if $x\in(-1,0)$,}\\0&\text{if $x=0$,}\\h(x)&\text{if $x\in(0,1)$,}\\-h^{-1}(x)&\text{if $x\in[1,\infty)$.}
\end{cases}
\end{align*}
It is not difficult to check that $f\circ f=g$, but, as you can see, the answer is less straightforward than it was in the complex case.
