Define the extremal Turán function $ex(n,G)$ of a graph $G$ as the most edges a graph on $n$ vertices can have without having a subgraph that is isomorphic to $G$. This function is known asymptotically if $G$ is non-bipartite but since it depends on the chromatic number of $G$, it is (at least) NP-hard to determine it. For some bipartite graphs the asymptotic/magnitude of $ex(n,G)$ is also known, but not for all. It is a conjecture that $ex(n,G)=\Theta(n^\alpha)$ for every $G$.
Algorithmically, how hard is it to determine $ex(n,G)$ for an input $G$?
For example, is it decidable whether $ex(n,G)=O(n^\alpha)$?