Consider the problem of deciding a language $L$; for concreteness, say that this is the graph isomorphism problem. That is, $L$ consists of pairs of graphs $(G, H)$ such that $G\simeq H$. Now the time complexity of deciding this problem as stated depends on how the graphs are encoded. For example, if one were to have a "canonical" encoding of graphs (such that encoding strings are in bijective correspondence with isomorphism classes of graphs) the problem would be $O(n)$, as we could decide whether $G\simeq H$ simply by comparing the string representing $G$ to the string representing $H$.

On the other hand, if we represent a graph via its adjacency matrix, the best known algorithm (according to Wikipedia) gives only a subfactorial bound. Now consider the time complexity of converting from one language to another. If we let $T_1, T_2$ be the time complexity of deciding languages $L_1$ and $L_2$ respectively, and $T_{ij}$ be the time it takes a Turing machine to take a string $S$ and output another string $S'$ which is in language $j$ if and only if $S$ is in language $i$. We have

$$T_1\leq T_2+T_{12}$$ $$T_2\leq T_1+ T_{21}$$

as given a string that we want to test for its belonging to $L_i$, we may run it through the translation $L_i \to L_j$ and then decide language $j$. Indeed, this is a special case of a trivial "triangle inequality" for translation; the time it takes to translate from $L_1$ to $L_2$ plus the time it takes to translate from $L_2$ to $L_3$ is greater than or equal to the time it takes to translate from $L_1$ to $L_3$. (I say it is a special case because a decision problem is the same as converting a language $L$ to the language $\{ 1 \}$.)

What I want to know is:

Can we better quantify the relationship between the time complexity of a decision problem and the nature of the encoding?

So that this question is not prohibitively vague, let us say that I am looking for (1) related references, and (2) a measure of the complexity of an encoding which more tightly relates to time complexity of the "underlying" decision problem.

Added (7/19/2010): The answers below, particularly Ryan Williams' excellent survey of the dependence of the time complexity of various problems on their encoding, get at the motivation to my question but not at my question itself. In particular, it's clear that every problem may be re-encoded to allow (say) $O(\log n)$ time complexity, by padding. My question is whether there's a reasonable way to measure this dependence.

For example, say the decision problem for $L_1$ is reducible to the decision problem for $L_2$, and vice versa, so that $L_1$ and $L_2$ in some sense represent the same problem. Is there a way to formalize this last statement (about "representing the same problem")? I am imagining, for example, a measure $C_i$ of the complexity of a language so that if $T_i$ is the time complexity of the language, and $L_1$ and $L_2$ are, say, easily reducible to one another, then $T_1/C_1\sim T_2/C_2$. (Of course $C_i=T_i$ works, but ideally $C_i$ would be somehow a property of the language, rather than the decision problem.) This is unfortunately becoming quite speculative, so again, related references would be a great answer.

definitionfor some other complexity measure. I haven't seen such a concept. I'm not sure why you distinguish between "decision problem" and "language"; for all intents and purposes these are the same. (I certainly have been using them interchangably.) $\endgroup$ – Ryan Williams Jul 19 '10 at 21:59