7
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ A sparse language is a language where the number of strings of length $n$ is bounded by a polynomial function of $n$. All unary languages are sparse. Mahaney's theorem says that if a sparse language is NP-complete, then P = NP. $\endgroup$
    – Pål GD
    Aug 7, 2013 at 13:47

4 Answers 4

8
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I like your pointer towards data strucutres. The runtime of many graph algorithms depends critically on the graph representation chosen, which can be seen as input encoding. $\endgroup$
    – Raphael
    Aug 8, 2013 at 10:33
6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ is there any rigorous definition of "natural encoding"? $\endgroup$
    – user774025
    Aug 7, 2013 at 9:16
  • 1
    $\begingroup$ @user774025, nope. Example: a natural encoding of an integer $x$ is to list the integer in binary form. A natural encoding of a list $L=[x_1,x_2,\dots,x_n]$ is the concatenation of the encoding of $x_1$, the encoding of $x_2$, etc. (with suitable delimiters). And so on. $\endgroup$
    – D.W.
    Aug 7, 2013 at 11:39
  • $\begingroup$ @user774025 In other words, no, there is not. $\endgroup$
    – Patrick87
    Aug 8, 2013 at 15:31
  • $\begingroup$ And an "unnatural" encoding would encode an integer x as x 1's, for example encode 7 as 1111111. $\endgroup$
    – gnasher729
    May 10, 2021 at 23:08
5
$\begingroup$

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

  • a non-unary encoding with
  • at most a constant factor overhead (over the bare information),

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ "Not exactly an answer to your question" -- is it a comment, then? ;) $\endgroup$
    – Raphael
    Aug 8, 2013 at 10:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.