Meta-computational complexity? Computational complexity asks the following question: Given a problem $P$, what is the time-cost of the lowest time-cost machine $M^*$ that solves $P$?

But this misses a certain aspect of the complexity of $P$, namely the complexity of finding $M^*$ in the space of machines. The problem of finding $M^*$ can be seen as an instance in the meta-problem of finding for some problem $P$ in a class class $\mathcal P$, a machine, or the optimal machine (according to some criterion) that solves $P$".


  The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$.


We could turn the set of problems $\mathcal P$ into a single problem $\tilde {\mathcal P}$, where the specification of which $P\in \mathcal P$ we want to solve, is defined within the information describing the instances of $\tilde {\mathcal P}$. However, an efficient machine $\tilde M$ that solves $\tilde {\mathcal P}$, can not necessarily be used to solve the meta-problem $\mathcal P$, since $\tilde M$ might not make use of specific possible optimizations for problems $P\in \mathcal P$. For example. the solution to some specific problem $P_i\in \mathcal P$ might be simply to always output $0$, in which case the solution to $\mathcal P$ for instance $P_i$, is a $C(1)$ complexity machine $M_i$ that ignores input and outputs $0$. But $\tilde M$ might instead do all kinds of complex computations, that still are below the worst-case bound for all problems in $\mathcal P$, but don't make use of this specific feature of the instance $P_i$. 

Hence it may be that some problem $P$ has very low computational-complexity, but high "meta-complexity" (i.e. for problems in the class of problems $\mathcal P$ that $P$ is a part of, it is hard to find an efficient algorithm).

Is there a theory akin to this type of "meta-complexity"?
The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$.


It's undecidable* whether a given Turing machine even solves&nbsp;$P$, let alone whether it's optimal according to some criterion.  Since your problem isn't computable even without resource bounds, there isn't really any scope for complexity theory.

And how are you going to specify the problem&nbsp;$P$ anyway, except by giving some Turing machine?

* Off the top of my head, probably not even recursively enumerable.