Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
The time complexity depends upon the encoding. The time complexities for $L$ and $L'$ could be arbitrarily far apart, given a crazy enough encoding.
In practice we usually care about the time complexity for a "natural" encoding. Often, if there are multiple "natural" encodings, then they all tend to lead to approximately the same time complexity (e.g., if you can convert between the encodings efficiently). However, there is no formal guarantee of this.
Therefore, technically speaking, one cannot speak of the time complexity of a problem without specifying the particular encoding used.
Consider any NP-complete language $L$ and its brute-force (hence exponential-time) solver $A$. Now define
$\qquad L' = \{ x\$0^{|x|^{|x|}} \mid x \in L \}$.
Now clearly, a slight adaption of $A$ (use input only up to $\$$) decides $L'$ in time exponential in $|x|$ and thus in time polynomial in the length of its own input (which is from $L'$). That is, $L' \in \mathsf{P}$.
A simpler consideration is to move from the standard binary to unary encoding. Suddenly, trivial primality checks and even factorisation run in polynomial time. This concept is related to pseudo-polynomial runtime.
So yes: the encoding matters if it changes the input length significantly. Therefore, the typical assumption is to use
as vague as that is.
Note that not even runtimes in terms of $\Theta$-classes are invariant using these assumption alone. Imagine an encoding of arrays that interleaves the numbers; this adds a polynomial factor to finding the maximum. So you should probably be careful even with "good" encodings if you want to say something with higher granularity than up to polynomial factors.
Not exactly an answer to your question, but the Berman-Hartmanis conjecture states (informally) that all NP-complete problems are encodings of each other, in some sense. The notion of encoding used in the conjecture does preserve time complexity, up to a polynomial difference.
