We propose an information-theoretic model for the space of computational problems by representing each problem as a finite binary object and measuring shared structure through algorithmic mutual information. This makes it possible to talk about local perturbations, global geometry, and the rarity of meaningful relationships inside a single formal framework.
The first ingredient is local: if two length-\(N\) problem descriptions differ in exactly \(k\) coordinates, then the perturbation can be specified by identifying the flipped coordinates, yielding the bound \[ K(Q\mid P)\le \log_2 \binom{N}{k}+O(\log N), \] and therefore a corresponding lower bound on \(I(P;Q)\). After normalizing by \(N\), this produces the entropy-shaped envelope \(1-H_2(k/N)\), which we use as a continuous similarity proxy on the Hamming cube.
The main structural contribution is global. Let \(\mathcal C_{\beta,N}\) be the set of length-\(N\) problems with Kolmogorov complexity at most \(\beta N\), and let \(\mathcal N_\alpha(\mathcal C_{\beta,N})\) denote their radius-\(\alpha N\) Hamming neighborhood. We prove that \[ \frac{|\mathcal N_\alpha(\mathcal C_{\beta,N})|}{2^N} \le 2^{-N(1-\beta-H_2(\alpha))+o(N)}. \] Thus, whenever \(\beta+H_2(\alpha)<1\), the union of all low-complexity seeds and all \(\alpha N\)-bit perturbations of those seeds occupies an exponentially vanishing fraction of problem space. This gives a precise sense in which structured regions are sparse, while the ambient geometry is dominated by near-independence.
The background notions are standard from algorithmic information theory: Kolmogorov complexity, chain-rule identities, and algorithmic mutual information as a measure of shared description length [1]. Closely related notions of universal similarity include information distance and normalized information distance, which measure how concisely one object can be transformed into another [2][3].
Our setup differs in two ways. First, we commit to an explicit edit model: a fixed length-\(N\) description space equipped with Hamming distance. This lets us turn shortest-translator intuition into concrete combinatorics using binomial coefficients and binary entropy [4]. Second, we emphasize a global geometric conclusion: not merely that nearby strings share information, but that the union of all neighborhoods around low-complexity seeds remains exponentially sparse below an explicit entropy threshold.
The broader complexity-theoretic literature on reductions to random strings is also relevant context [5]. The present paper does not attempt a resource-bounded characterization. Instead, it gives an unbounded geometric model that isolates a necessary informational feature of reducibility: short translators can only exist where substantial shared algorithmic structure already exists.
We represent a computational problem by a binary description
This should be read as a modeling choice, not a claim about a unique canonical encoding. The description could stand for a bounded truth table, a circuit, a verifier, a finite slice of an instance language, or any fixed encoding of a computational object. What matters is that once problems are placed in a common finite description space, we can talk about edits, distances, and shared structure in a mathematically controlled way.
We write \(K(P)\) for the prefix Kolmogorov complexity of \(P\), that is, the length of the shortest self-delimiting program on a fixed universal machine that outputs \(P\) [1]. For fixed-length strings of length \(N\), switching between common Kolmogorov-complexity conventions only changes expressions by lower-order additive terms, so the asymptotic statements below are unaffected.
For two objects \(P,Q\), let \(K(P,Q)\) denote the complexity of the pair under a standard computable pairing function, and define algorithmic mutual information by
We repeatedly use the chain-rule form
where \(P^*\) is a shortest program for \(P\). Rearranging gives
This identity is the right lens for the rest of the paper. It says that shared information is exactly the amount by which knowledge of \(P\) shortens the description of \(Q\), up to logarithmic bookkeeping.
Once problem descriptions live in \(\{0,1\}^N\), the most elementary perturbation is to flip a bit. This places the model inside the \(N\)-dimensional Hamming cube, where adjacency corresponds to one-bit edits and Hamming distance counts the number of required flips.
Let \(P,Q\in\{0,1\}^N\) and write
If \(P\) and \(Q\) differ in exactly \(k\) coordinates, then relative to \(P\), the only remaining uncertainty in specifying \(Q\) is which \(k\) coordinates were changed. That simple counting idea is the source of the local entropy envelope.
Let \(P,Q \in \{0,1\}^N\) satisfy \(d_H(P,Q)=k\). Then
and consequently
In particular, if \(K(Q)\ge N-c\), then
Let \(S\subseteq \{1,\dots,N\}\) be the set of coordinates on which \(P\) and \(Q\) differ, so \(|S|=k\). Given \(P\), it is enough to encode the subset \(S\) and then flip those coordinates. One may describe \(S\) by first encoding \(k\) in \(O(\log N)\) bits and then encoding the rank of \(S\) among all \(k\)-subsets of \(\{1,\dots,N\}\), which takes \(\lceil \log_2 \binom{N}{k}\rceil\) bits. A fixed decoding routine reconstructs \(S\) and applies the flips to \(P\). Therefore
Next, by the chain rule,
Since a shortest description \(P^*\) computes \(P\), conditioning on \(P^*\) is at least as informative as conditioning on \(P\), up to an additive constant. Hence
and so
If \(K(Q)\ge N-c\), substitute this into the last display and divide by \(N\). \(\square\)
The point of Proposition 1 is conceptual as much as technical. A \(k\)-bit perturbation does not destroy all structure. It only injects the combinatorial uncertainty associated with choosing one element from a Hamming sphere of radius \(k\). For incompressible strings, the lost shared information is therefore controlled by the logarithm of that sphere size.
For \(k=xN\), the standard asymptotic \(\frac{1}{N}\log_2 \binom{N}{xN}=H_2(x)+o(1)\) follows from Stirling's formula and is classical in information theory [4].
Proposition 1 is discrete, but its shape becomes much clearer after normalizing distance by \(N\). Let
In the incompressible regime, the lower bound from Proposition 1 becomes
at least up to truncation at zero and lower-order terms. This suggests a natural computable proxy for local information similarity.
For \(P,Q\in\{0,1\}^N\), define
Using the entropy approximation, this is asymptotically
This kernel is not claimed to be the exact mutual information. Rather, it is a principled envelope derived from a concrete edit model. It turns the combinatorics of Hamming spheres into a continuous landscape in which nearby descriptions sit in high-similarity regions and typical mid-radius pairs fall into a low-similarity basin.
The local picture raises the real geometric question. It is one thing to say that a neighborhood around a particular structured seed contains high-similarity points. It is another to ask whether the union of all such neighborhoods occupies a substantial fraction of the ambient space. That is the main global theorem.
For \(0\le \beta \le 1\), define the low-complexity set
For \(0\le \alpha < 1/2\), define its radius-\(\alpha N\) neighborhood by
Intuition. There are two competing exponentials. The number of low-complexity seeds grows like \(2^{\beta N}\), while each Hamming ball of relative radius \(\alpha\) grows like \(2^{N H_2(\alpha)}\). The theorem says that these exponentials simply multiply. As long as their combined exponent stays below \(1\), even the union of all such balls still occupies an exponentially vanishing fraction of the entire cube.
Let \(0\le \alpha < 1/2\) and \(0\le \beta \le 1\). Then
In particular, if
then a uniformly random \(Q\in\{0,1\}^N\) lies outside \(\mathcal N_\alpha(\mathcal C_{\beta,N})\) with probability \(1-2^{-\Omega(N)}\).
First, the number of strings of prefix complexity at most \(m\) is at most \(2^{m+1}-1\) [1]. Therefore
Next, for any fixed center \(P\in\{0,1\}^N\), the radius-\(\lfloor \alpha N\rfloor\) Hamming ball satisfies
uniformly for every fixed \(0\le \alpha < 1/2\) [4]. Hence, by the union bound,
Dividing by \(2^N\) gives
If \(\beta+H_2(\alpha)<1\), then the exponent is negative, so the right-hand side is exponentially small in \(N\). The final probabilistic claim is exactly the same statement interpreted under the uniform measure on \(\{0,1\}^N\). \(\square\)
This is the paper's main global statement. Proposition 1 says that a low-radius perturbation preserves a large information budget relative to its center. Theorem 1 says that even after taking the union over all low-complexity centers, those structured neighborhoods still fail to fill more than an exponentially tiny part of the ambient space unless the entropy threshold is crossed.
Theorem 1 exposes a sharp structural parameter:
The term \(\beta\) measures how much description complexity is allowed in the center, while \(H_2(\alpha)\) measures how quickly a Hamming ball expands at relative radius \(\alpha\). Their sum therefore acts as an effective dimension of the structured region. Below the threshold, the region is exponentially sparse. At the threshold, the exponential upper bound becomes order one. Above it, a crude union bound no longer rules out macroscopic coverage.
This is exactly the sort of statement the landscape picture was meant to produce. The local entropy envelope identifies what it costs to move around inside a structured pocket; the global threshold identifies when even the totality of those pockets remains negligible inside the full space of problems.
The opposite regime is the generic one: unrelated random descriptions. In that case, the global landscape is dominated by near-independence rather than by short translators.
Let \(P,Q\) be independent uniformly random strings in \(\{0,1\}^N\). Then with probability \(1-o(1)\),
Fix \(t\ge 1\). For any fixed shortest description \(P^*\), the number of strings \(Q\in\{0,1\}^N\) satisfying
is at most \(2^{N-t}-1\), because there are fewer than \(2^{N-t}\) self-delimiting programs of length less than \(N-t\) [1]. Since \(Q\) is uniform over \(2^N\) strings, it follows that
Therefore, with probability at least \(1-2^{-t}\),
On the other hand, always \(K(Q)\le N+O(1)\). Using
we get, with probability at least \(1-2^{-t}\),
Taking \(t=\lceil 2\log_2 N\rceil\) yields \(I(P;Q)=O(\log N)\) with probability \(1-O(N^{-2})\), and in particular with probability \(1-o(1)\). \(\square\)
Proposition 2 supplies the ambient baseline: typical pairs of random problem descriptions share essentially no reusable algorithmic structure beyond logarithmic overhead. Thus the low-similarity basin in the landscape is not a pathological corner case. It is the generic background.
In this framework, a reduction can be idealized as a short translator: a program that reconstructs one problem description from another. This is deliberately more primitive than a standard many-one or Turing reduction, because it ignores uniformity and resource bounds. But it isolates a necessary informational condition that any reduction-like relationship must satisfy.
Suppose there exists a program \(R\) of length \(r\) such that \(R(Q)=P\). Then
Since conditioning on \(Q^*\) can only help up to constants,
So genuinely short translators force large shared algorithmic information. This observation aligns with the landscape viewpoint:
In that sense, reducibility is not geometrically generic. It is concentrated in rare pockets where descriptions are close enough, or structured enough, for information to be reused.
The complexity-theoretic study of reductions to sets of random strings is much subtler in resource-bounded settings [5]. The present paper should therefore be read as an unbounded geometric model rather than as a direct characterization of standard complexity classes.
The full picture is now coherent. The Hamming cube provides a discrete ambient space for problem descriptions. Local perturbations produce an entropy-controlled information envelope. The continuous kernel \(S_N\) turns that envelope into a smooth similarity landscape. Theorem 1 shows that structured pockets remain exponentially sparse below the threshold \(\beta+H_2(\alpha)=1\). Proposition 2 shows that the generic background is a near-independent sea.
This makes the phrase problem information landscape mathematically concrete. It is not just that some problems are similar and others are not. Rather, the geometry has a specific large-scale shape: a small family of structured basins embedded inside a vast region where shared algorithmic content is negligible.
Representing computational problems as finite binary objects gives a simple but surprisingly expressive geometric model. The local combinatorics of bit flips already imply a nontrivial information envelope, and that envelope induces a natural continuous similarity kernel on problem space.
The main new conclusion is global: neighborhoods around low-complexity seeds remain exponentially sparse unless the entropy growth of the Hamming ball compensates for the scarcity of the seeds themselves. This makes the central structural message crisp. Meaningful relations between problems are not spread uniformly through the space of descriptions; they are concentrated in thin, highly structured regions.
A natural next step is to seek resource-bounded analogues of the same picture, replacing unbounded Kolmogorov complexity by time- or space-bounded variants. That would move the landscape from an informational model of reducibility toward a fully complexity-theoretic one.