Consider the problem of deciding a language $L$; for concreteness, say that this is the [graph isomorphism problem](http://en.wikipedia.org/wiki/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](http://en.wikipedia.org/wiki/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.



What is the relationship between "translation" and time complexity?
When it comes to the time complexity of problems, the encoding of the problem can be totally crucial. In general, the encoding of the problem cannot be separated from the complexity of the problem itself. 


The first canonical example of this (as mentioned before in [answering another question](https://mathoverflow.net/questions/31796/exptime-algorithms/31805#31805)) can be seen with the following two problems:


(1) *Given a deterministic Turing machine $M$, string $x$, and integer $k$ **written in binary**, does $M$ accept $x$ within $k$ steps?*


Problem (1) is $EXPTIME$-complete. However the following problem is $P$-complete:


(2) *Given a deterministic Turing machine $M$, string $x$, and integer $k$ **written as a string of $k$ ones**, does $M$ accept $x$ within $k$ steps?*


So already, the way in which $k$ is represented in an instance completely determines the complexity of the problem. (Note if I wrote $k$ in ternary, $4$-ary, etc., problem (1) remains $EXPTIME$-complete.)


Another interesting example comes from circuit complexity. Consider the following two problems:


(3) *Given a truth table of $2^n$ bits for a function* $f:$ {$0,1$}$^n \rightarrow ${$0,1$}*, return a circuit with AND/OR/NOT gates that computes $f$ and contains a minimum number of gates.*


(4) *Given a function* $f:$ {$0,1$}$^n \rightarrow ${$0,1$} *represented as a circuit with AND/OR/NOT gates, return a circuit that also computes $f$ and contains a minimum number of gates.*


Problem (3) can be easily seen to be in $NP$, since the minimum circuit for $f$ needs at most $O(2^n/n)$ gates, and checking that a given circuit works for $f$ takes $2^{O(n)}$ steps. However (3) is not known to be in $P$, nor is it clear that it's $NP$-complete. The curious status of (3) is discussed in



> 
> Valentine Kabanets, Jin-yi Cai: Circuit minimization problem. STOC 2000: 73-79
> 
> 
> 


What about problem (4)? It is *not* known to be in $NP$! It is known to be in $\Sigma\_2 P$ of the polynomial time hierarchy, but not known to be complete for that class. However the version where you use the representation of *formulas* instead of circuits is known to be $\Sigma\_2 P$-complete under Turing reductions:



> 
> David Buchfuhrer, Christopher Umans: The Complexity of Boolean Formula Minimization. ICALP (1) 2008: 24-35
> 
> 
> 


Examples of this sort are everywhere in complexity theory, simply because the encoding can really matter if the relative sizes of encodings (or the complexities of encodings) are different enough. Luckily, most "natural" encodings (for which there are polynomial time mappings from one encoding to another) do not seem to affect the overall complexity of a problem (e.g. whether or not a problem is in $NP$). This is another reason why the notion of polynomial time is one of the main focuses in complexity. It is a "robust" notion that isn't affected by whether you use e.g. adjacency lists versus adjacency matrices to represent a graph in your graph problem. Related to this, there is a recent and thought-provoking reference that outlines a complexity theory for succinctly represented graphs (graphs whose adjacency matrices are the truth tables of small size circuits):



> 
> Sanjeev Arora, David Steurer, Avi Wigderson: Towards a Study of Low-Complexity Graphs. ICALP (1) 2009: 119-131 
> 
> 
> 


Finally, concerning your proposed "isomorphism-respecting" encoding of graphs: while it would be very neat to have, it would not be considered natural, since we don't know how to efficiently obtain such an encoding from any of the other encodings that have already been deemed natural.


**UPDATE TO ADDRESS YOUR REVISED QUESTION:** I think it is a neat idea to try to study "problems" as classes of languages that "represent the same thing" in some strong sense. I'm not aware of significant prior work on this (other than the cheap reply that "all NP-complete problems represent the same thing", which I don't think is what you are driving at). The closest reference I can think of is a related attempt to define "algorithm" in a similar way. See Blass, Dershowitz, and Gurevich's cool paper: <http://research.microsoft.com/en-us/um/people/gurevich/Opera/192.pdf>


