Many important results in computational complexity theory, and in particular "structural" complexity theory, have the interesting property that they can be understood as fundamentally following (as I see it...) from algorithmic results giving an efficient algorithm or communication protocol for some problem. These include the following:
- IP = PSPACE follows from a space-efficient recursive algorithm simulating interactive protocols, and an efficient interactive protocol for evaluating totally quantified boolean formulae. In fact any complexity class equality A=B can be seen as following from two efficient algorithms (an algorithm for problems in A which is efficient with respect to B, and vice versa).
- Proving NP-completeness of some problem is just finding an efficient algorithm to reduce an NP-complete problem to it.
- The (arguably!) crucial ingredient in the Time Hierarchy Theorem is an efficient universal simulation of Turing machines.
- The recent result of Ryan Williams that ACC $\not \supset$ NEXP is based on an efficient algorithm to solve circuit satisfiability for ACC circuits.
- The PCP Theorem is that efficient gap amplification is possible for constraint satisfaction problems.
- etc., etc.
My question (which is possibly hopelessly vague!) is as follows: Are there any important results in structural complexity theory (as distinct from "meta-results" like the relativisation barrier) which are not known to have a natural interpretation in terms of efficient algorithms (or communication protocols)?