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

• Can you add a very specific example? It should define what is $\mathcal P$, a class of problem and several instances of $\mathcal P$ as well as "some resource constraints". – John L. May 3 '19 at 15:09

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.

• "It's undecidable* whether a given Turing machine even solves $P$". For arbitrary problems and arbitrary turing machines, yes. The problem statement doesn't make those restrictions. This is like saying "some problems are undecidable, hence there is no space for computational complexity in any problem" – user56834 May 2 '19 at 11:40
• "And how are you going to specify the problem P anyway, except by giving some Turing machine?" you could use a Turing machine to specify the problem, yes. E.g. a very inefficient one. Or in terms of a logical formula that describes the problem. – user56834 May 2 '19 at 11:42
• @user56834 A logical formula in what language? Even second-order logic can only define problems in NP. (And that still doesn't get around the fundamental decidability issues.) – David Richerby May 2 '19 at 12:51
• Do you consider this to be arguments against my question? I'm honestly not quite sure what you're trying to say. Are you arguing that there is literally zero interesting things to be said about "meta-complexity", because we can't do this for literally arbitrary problems? I also don't see why you're making the point about about decidability. I agree that this would be a limitation on the scope of "meta-complexity", but you seem to be arguing that it means that literally nothing can be said about "meta-complexity"? Am I misinterpreting you? – user56834 May 2 '19 at 13:07
• I'm saying that everything in what you're calling "meta-complexity" is highly undecidable, which contradicts the whole essence of complexity. Complexity asks the question "What resources does a Turing machine need to do $X$?" but the answer to every question in "meta-complexity" is "Turing machines can't do that, regardless of what resources you give them." As a side issue, I'm pointing out that input representation is a big problem, but the fact that everything's undecidable already seems to blow everything out of the water. – David Richerby May 2 '19 at 14:08

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.

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

• "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" I wasn't assuming the input is finite. I also didn't specify how it would be infinite (more accurately, unbounded), but that's because I'm asking whether a theory on roughly this topic exists. I'm not proposing the theory myself. Apart from this, yes the minimum circuit size problem is interesting, thank you. :) – user56834 May 2 '19 at 9:25