What is the relationship between "translation" and time complexity?

Question

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.

Answer 1

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) 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

Answer 2

The general abstract setting for the issue driving your question is the notion of reduction of equivalence relations. The idea of this is that one equivalence relation $E$ reduces to another $F$ with respect to some complexity concept if there is a function $f$ in this class such that

• $x\, E\, y$ if and only if $f(x)\, F\, f(y)$

You can imagine that $E$ is the equivalence relation arising from one way of representing mathematical objects (graphs, algebraic structures, whatever) and $F$ is the relation corresponding to an alternative method. The reduction is saying that equivalence with respect to the $E$ way of representing the objects is no more difficult than equivalence with respect to the $F$ way of representing them.

I claim that understanding this reducibility relation amounts to understanding exactly what your question is aimed at, the question of how one manner of representing the same objects can be simpler than another. More generally, this reducibility relation provides a very precise way to understand what it means to say that one classification problem is strictly harder than another, even when the objects in the two cases seem totally unrelated at first.

In the case you seem most interested, you could regard $E$ and $F$ as NP equivalence relations and insist that $f$ is polynomial time computable. This is a case that has been recently investigated by Sy Friedman, and this MO question arose out of a talk he gave on this topic here in New York, and discusses as motivation some of the relevant general theory. This appears to be a completely new research area, ripe for progress. I would encourage anyone to enter into it.

Much of that theory is inspired by the enormous successes of the much more developed instance of this concept, occurring when $E$ and $F$ are Borel relations on the reals and $f$ is a Borel function. This case is the emerging-but-possibly-now-mature field of Borel equivalence relation theory (see Greg Hjorth's survey article and Simon Thomas' notes). The theory of Borel equivalence relation theory has to deal explicitly with the Borel analogues of the precise issues you mention in your question, and has made huge illuminating progress in understanding the structure of Borel equivalence relations under Borel reducibility. I mention some of the basic results in this MO answer.

In general, for each notion of complexity, the goal is to study the whole hierarchy of equivalence relations, to discover its features and general structural results. The Borel case is quite well developed by now, exhibiting many fascinating features, but the NP case is much less well developed. I do know personally, however, that other researchers are working on several other natural contexts of this idea.

Answer 3

A legit encoding would give two different codings for two different objects. The problem of, for instance, graph isomorphism only makes sense if one considers two isomorphic graphs to be different. There are tons of problems for which changing the encoding leads to a classification in a smaller complexity class. Take for example (Garey & Johnson, p. 159), LINEAR DIVISIBILITY, which is, given integers $a$ and $c$ the problem of answering $(\exists x)[ax +1|c]$. This problem is $\gamma$-complete, but trivially in P if the inputs are given in unary. G&J add "[The] supposed intractability [of LINEAR DIVISIBILITY] depends heavily on the convention that numbers be represented by strings having length logarithmic in their magnitudes."

You should in particular check the notion of "pseudo-polynomial time" and section 4.2 of Garey & Johnson.

Hope this helps.

Answer 4

Your question reminded me of matroid problems. With these it is of great importance to specify how the input is given, as translating between input forms can increase the size of the input exponentially. There is a survey of this issue here:

http://arxiv.org/abs/math/0702567