Does the time complexity of a problem change with encoding of the problem?

Suppose I have a decision problem $D$ and I encode it to a language $L \subset \{0,1\}^*$. Now, I can also encode it to a different language $L'$.

Is there any theorem relating the time complexity of $L$ and $L'$?

How does the time complexity of a problem change with different encodings of the same problem?

Yes, the complexity depends on the encoding. The only thing you can be sure of is that if translating from encoding $L$ to encoding $L'$ or vice versa has the complexity $f$, and $D$ can be solved with complexity $g$, then $D'$ (same problem expressed with the encoding $L'$) can be solved with complexity $O(f+g)$ by going back and forth between encodings.

It isn't just a matter of length of the encoding. To give a simple example, let $L$ be positive integers represented in binary, and $L'$ be positive integers represented by their prime factorization. There is a polynomial bound in the size of one representation in terms of the other. Yet for a long time, it was not known whether primality testing can be solved in polynomial time in the binary representation; but in the factorization representation, it's trivially polynomial (probably $O(1)$ depending on the representation details).

Or consider the decision problem “is integer $n$ a member of set $S$”. If the set is represented by an unordered list of integers, this problem evidently requires at least linear time. But if the set is represented by a balanced search tree, lookup time is polylogarithmic in the size of the set.

In most concrete cases, there is an evident representation that everyone assumes, or more precisely there is a class of representations that are all equivalent up to a transformation that takes negligible time. But sometimes the representation is relevant, most frequently when analyzing data structures with more precision than polynomial time.

StackExchange Computer Science Q#13640, answer score: 8