Binary Encoding is Compact

Binary encoding represents a number $W$ in $\lceil {\log }_2(W+1)\rceil$ bits. In unary, the same number needs $W$ symbols. The gap between the two is exponential.

This compactness is usually treated as a harmless implementation detail, but it is not. It reshapes the boundary between tractable and intractable.

The Hidden Exponential

A dynamic programming algorithm for the subset sum problem runs in $O(nW)$. Under unary encoding, $W$ is proportional to the input length, so the algorithm is ordinary polynomial time. Under binary encoding, $W$ can be exponentially larger than the input length, so the same algorithm is exponential. The problem is weakly NP-hard precisely because its hardness evaporates when numbers are small, which is exactly what unary encoding enforces.

A dynamic programming table with dimensions $S_1\times S_2$ contains exactly $S_1\cdot S_2$ cells. For an instance $I$, let

$${\ell }_1(I)=\lceil {\log }_2(S_1+1)\rceil \text{and}{\ell }_2(I)=\lceil {\log }_2(S_2+1)\rceil$$

be the bit-lengths of the two numeric fields. Then

$$S_1\approx 2^{{\ell }_1(I)}\text{and}{S}_2\approx 2^{{\ell }_2(I)},$$

so the total number of cells is

$$S_1\cdot S_2\approx 2^{{\ell }_1(I)}\cdot 2^{{\ell }_2(I)}=2^{{\ell }_1(I)+{\ell }_2(I)}.$$

The algorithm is polynomial in the numeric values $S_1$ and $S_2$, yet exponential in the number of bits ${\ell }_1(I)+{\ell }_2(I)$ that encode them. The loops hide an exponential blow-up inside what looks like a simple double iteration.

Bi Knapsack is a concrete instance of this pattern. Its dynamic programme uses a table $T[i,s_1,s_2]$, so its running time is

$$O(n{S}_1{S}_2).$$

This is polynomial in the numeric capacities, but not necessarily polynomial in the encoded input. For instances with $S_1=S_2=2^{L(I)}$, each capacity needs only $L(I)+1$ bits, while the table has

$$(S_1+1)(S_2+1)=\Theta (2^{2L(I)})$$

capacity states. This is the exact sense in which the dynamic programme is pseudo-polynomial.

When Encoding Does Not Matter

Not every problem is rescued by unary encoding. A strongly NP-hard problem remains intractable even when every numeric parameter is bounded by a polynomial in the input length. The hardness comes from combinatorial structure, not from numeric magnitude.

Consider the travelling salesman problem. Its input is a graph with $n$ vertices and edge weights. Even if all weights are restricted to $\{0,1,2\}$ and written in unary, the problem is still NP-hard. The exponential search space of $n!$ permutations does not shrink when the numbers are small. No pseudo-polynomial algorithm is known, and none exists unless $\mathrm{P}=\mathrm{NP}$.

The weights are tiny, but the number of tours grows factorially. Unary encoding makes the weight labels longer, yet the permutation space is unchanged. The algorithm must still enumerate an exponential number of structures.

The Quantity Space

The clean dichotomy has a deeper cause. The question is whether the problem’s difficulty comes from iterating over a space whose size is a direct function of the numeric values themselves.

For the subset sum problem, the dynamic programming table has dimensions $n\times W$. The state space size is proportional to $W$ itself:

$$f(W)=W\approx 2^{{\ell }_W(I)}.$$

The function is essentially the identity on the numeric value. Because binary encoding compresses $W$ into ${\ell }_W(I)$ bits, iterating over all values up to $W$ implicitly iterates over $2^{{\ell }_W(I)}$ states. The exponential blow-up is hidden inside the loops.

For the travelling salesman problem, the search space is the set of all permutations of vertices:

$$f(|V|)=|V|!.$$

The edge weights are merely coefficients in the objective function. Restricting weights to $\{0,1,2\}$ does not reduce $|V|!$. The combinatorial explosion comes from the factorial of the vertex count, not from any numeric magnitude.

Even if we treat $|V|$ itself as a binary-encoded number with bit-length ${\ell }_V(I)$, so that $|V|\approx 2^{{\ell }_V(I)}$, the search space $|V|!$ is already super-polynomial in $|V|$. Under unary encoding the input length becomes $\Theta (|V|)$, yet $|V|!$ is still not polynomial in $|V|$. The encoding of the vertex count does not matter because the combinatorial explosion outruns the compression.

Uniform Polynomial Bounds

Fix an encoding of problem instances, and let $m(I)=|I|$ be the length of instance $I$ under that encoding. An algorithm is polynomial-time if there exist fixed constants $C$ and $c$ such that

$$\forall I:T(I)\le C\cdot m(I{)}^c.$$

The encoding is fixed for the problem. It is not chosen separately for each instance. Polynomial-time solvability is stable under standard encodings whose lengths are polynomially related. Binary and unary encodings of numeric values are not polynomially equivalent, since a value $W$ has binary length $\Theta (\log W)$ but unary length $\Theta (W)$.

The exponent $c$ is chosen once for the whole algorithm. It cannot change with the instance. In particular, one cannot prove polynomial time by saying that, for each instance $I$, there exists some exponent $c(I)$ with

$$T(I)\le m(I{)}^{c(I)}.$$

That would be meaningless: almost any finite runtime can be bounded this way by choosing a large enough instance-dependent exponent.

Now let $q(I)$ be a numeric quantity used by the algorithm, and define its binary length by

$${\ell }_q(I)=\lceil {\log }_2(q(I)+1)\rceil .$$

Every non-negative integer satisfies $q(I)\approx 2^{{\ell }_q(I)}$. This alone says nothing about polynomial time. What matters is whether there is a fixed exponent $d$ such that

$$\forall I:q(I)\le m(I{)}^d.$$

If such a $d$ exists, then iterating over $q(I)$ values can still be polynomial in the input length. If no such fixed $d$ exists, then iterating over $q(I)$ values may be exponential in the input length.

Minimum Search

For minimum search, the input is an explicit array

$$I=(a_1,a_2,\dots ,a_N).$$

Here $q(I)=N$. Since the instance explicitly contains $N$ entries,

$$N\le m(I).$$

So we can choose the fixed exponent $d=1$:

$$q(I)=N\le m(I{)}^1.$$

A linear scan therefore satisfies

$$T(I)=O(N)\le O(m(I)).$$

This is polynomial-time with the fixed exponent $c=1$.

Subset Sum

For subset sum, the input contains a target value $W$ as one binary field:

$$I=(w_1,\dots ,w_n,W).$$

Here $q(I)=W$. The field $W$ has length

$${\ell }_W(I)=\lceil {\log }_2(W+1)\rceil .$$

There is no fixed exponent $d$ such that

$$\forall I:W\le m(I{)}^d.$$

For every fixed $d$, one can choose an instance with $W$ so large that

$$W>m(I{)}^d.$$

Equivalently, ${\ell }_W(I)$ may be linear in $m(I)$, so

$$W\approx 2^{{\ell }_W(I)}$$

may be exponential in the input length. The dynamic programming algorithm creates $W+1$ columns, so

$$T(I)=O(nW)=O(n{2}^{{\ell }_W(I)}),$$

which is not bounded by $m(I{)}^c$ for any fixed $c$.

Summa summarum:

$$\begin{array}{cccc}\text{problem}& q(I)& \text{fixed polynomial bound}& \text{result}\\ \text{minimum search}& N& N\le m(I{)}^1& \text{polynomial}\\ \text{subset sum DP}& W& \text{no fixed }d\text{ with }W\le m(I{)}^d& \text{pseudo-polynomial}\end{array}$$

So the point is not that ${\ell }_q(I)$ exists. It always exists. The point is whether the exponent bounding $q(I)$ by $m(I)$ is a fixed constant independent of the instance.

Beyond NP-Hardness

This gives the clean dichotomy. For weakly NP-hard problems, the hardness lives in the encoding gap because the state space grows with the numeric value. For strongly NP-hard problems, the hardness lives in the combinatorial structure, and no amount of decompression can remove it.

This means the complexity class of a weakly NP-hard problem can depend on how its input is written. The hardness can come from numeric parameters being compressed efficiently. Remove the compression, and that source of hardness disappears.

Therefore, binary encoding is not just compact—it is the source of the exponential gap that makes weakly NP-hard problems intractable.