Meta-computational complexity?

Question

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"?

Answer 1

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 $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 $P$ anyway, except by giving some Turing machine?

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

Answer 2

It sounds to me that you're interested in complexity of preprocessing.

I'll state your question in a different way. We have a problem $P$ consisting of pairs $(x,y)$ that satisfy some condition. We'd like an algorithm which (1) takes $x$, (2) can perform a lot of computation (preprocessing), (3) finally it's given $y$ and needs to output quickly whether $(x,y) \in P$. This is the setting of parameterized complexity, a huge field.

Answer 3

As long as you don't take proper care to distingish between finite input and infinite input, and implicitly assume that the input is always finite (since you made no attempts at specifying how infinite input would be given), it just boils down to compress the set of (input,output) pairs suitably according to your resource constraints. There are theories of compression under resource constraints (google for "resource bounded kolmogorov complexity).

Of course, you can say that a 64-bit computer will be limited in the problem instance descriptions which it can interpret naturally, and that hence you can limit the input to be finite in natural ways. If the input and output should still be separated, and just the description of the function (a relation would be a function with output 0 or 1) which computes input to output mapping, than you might google for "minimum circuit size problem".