# Enumerating Complexity Revisited

Alexander Shekhovtsov
Moscow Institute of Physics and Technology
<EMAIL_ADDRESS>Georgii Zakharov
Moscow Institute of Physics and Technology
<EMAIL_ADDRESS>
## Abstract

Consider a subset of positive integers $S$. In this paper, we reduce the upper
bound on the length of a minimum program that enumerates $S$ in terms of the
probability of $S$ being enumerated by a random program.

So far, the best-known upper bound was given by Solovay. Solovay proved that
the minimum length of a program enumerating $S$ is bounded by $3$ times minus
binary logarithm of the probability that a random program enumerates $S$.
Later, Vereshchagin showed that the constant can be improved from $3$ to $2$
for finite sets. By improving the method proposed by Solovay, we demonstrate
that any bound for finite sets implies the same bound for infinite sets,
modulo logarithmic factors. Thus, the constant can be replaced by $2$ for
every set $S$ due to the result of Vereshchagin.

## Organization

In Section 1, we introduce definitions of deterministic and randomized
Kolmogorov complexity of a set. Then, we present the results known prior to
our work. After that, we formulate the main result of the paper in Theorem
1.3. In Section 2, in order to prove Theorem 1.3, we describe the notions of
cats and ants. Both cats and ants move along the edges of the graph $G$
described in Subsection 2.1. The position of cats at time $t$ is equal to the
set enumerated by the deterministic machine halted after $t$ steps. Similarly,
the position of ants at time $t$ is equal to the set enumerated by the
randomized machine halted after $t$ steps. Then, we introduce shadow positions
for the ants, which will follow the ants with some delay. We describe how the
shadow positions will mimic the real ones. The shadow positions will
correspond to an another randomized machine $M^{\prime}$, which is used in the
proof of the Theorem 1.3. After that, we are finally able to state Lemma 2.1.
Lastly, we prove that Theorem 1.3 follows from Lemma 2.1. In Section 3, we
prove Lemma 2.1. Section 4 contains a discussion of the results.

##  1 Introduction

To formulate the main results of this work, we will introduce the concepts of
complexities for deterministic and probabilistic enumerating machines.

###  1.1 Deterministic Enumerating Machine

Consider a deterministic machine $D$. $D$ takes a binary string as an input
and enumerates a subset of natural numbers. $D$ is not required to halt and
may enumerate an infinite set. Let us define the complexity of a set
$S\subset\mathbb{N}$, denoted as $I_{D}(S)$, as the minimum length of an input
for $D$ on which it enumerates $S$. If there is no such input, then
$I_{D}(S)=\infty$. By a standard theorem, there exists a machine $D_{0}$ such
that for any other machine $D,$ there is a constant $c$ such that:

$I_{D}(S)\leq I_{D_{0}}(S)+c$

The machine $D_{0}$ is referred to as universal. Set $D$ equal to any such
universal machine $D_{0}$ and define $I(S)$ as $I_{D}(S)$. Thus, $I(S)$ is
well-defined up to an additive constant.

###  1.2 Probabilistic Enumerating Machine

Consider a probabilistic machine $M$ that utilizes arbitrarily many random
bits, uniformly distributed and independent, and enumerates a subset of
natural numbers. Similarly to the deterministic machine, $M$ is not required
to halt and may enumerate an infinite set. Such a machine defines a mapping
from the Cantor space $\Omega$ (all infinite sequences of zeros and ones) to
the family of subsets of the natural numbers. An outcome $w\in\Omega$ of the
random bits corresponds to the set that is enumerated by $M$ when $w$ is used
as input as a sequence of random bits. The image of uniform measure then
becomes a measure on the set of all subsets of the natural numbers, and this
is the measure we refer to when discussing the probability (for machine $M$)
of enumerating a certain set $S$. This probability is non-zero only if the set
$S$ is enumerable, as implied by a variant of the de
Leeuw–Moore–Shannon–Shapiro theorem for enumeration problems [2]. We define
the complexity $H_{M}(S)$ as the negative binary logarithm of the probability
that $M$ enumerates $S$: $H_{M}(S)=-\log_{2}Pr(M\ \textit{enumerates}\ S)$. If
this probability is zero, we consider the complexity to be infinite.

Similar to the deterministic case, there exists a machine $M_{0}$ in such a
way that for any other $M,$ there is a constant $c$ such that:

$H_{M}(S)\leq H_{M_{0}}(S)+c$

Such a machine $M_{0}$ is referred to as optimal. Set $M$ equal to any such
optimal machine $M_{0}$ and define $H(S)$ as $H_{M}(S).$ Therefore, $H(S)$ is
well-defined up to an additive constant.

###  1.3 Connection Between Deterministic and Randomized Complexity

Since $M$ can generate an input $x$ for machine $D$ using $|x|+O(\log|x|)$ of
its random bits (for instance, one can first generate the length $|x|$ and
then $x$ itself), it is true that $H(S)\leq I(S)+O(\log I(S))$ for all
$S\subset\mathbb{N}$.

However, obtaining the converse inequality is more challenging. Solovay proved
a linear upper bound.

######  Theorem 1.1.

(Solovay, [4]). There exists a constant $c$ such that for any
$S\subset\mathbb{N}$, it holds that $I(S)\leq 3\cdot H(S)+2\log H(S)+c.$

Later, Vereshchagin improved the constant from three to two for finite sets:

######  Theorem 1.2.

(Vereshchagin, [5]). There exists a constant $c$ such that for any finite
$S\subset\mathbb{N}$, it holds that $I(S)\leq 2\cdot H(S)+2\log H(S)+c.$

Vereshchagin also asked the question whether it is possible to improve the
Solovay’s bound by reducing the length of an auxiliary string in the Solovay’s
algorithm. We answer positively to this question. We will show how to extend
any upper bound for finite sets to infinite sets. This result is formulated in
the following theorem.

######  Theorem 1.3.

Let $\alpha\geq 1$ be such that for any finite $S\subset\mathbb{N}$,

$I(S)\leq\alpha\cdot H(S)+O(\log H(S))$

Then the same bound holds for any infinite $S$ (possibly with a different
O-big).

Applying this Theorem 1.3 to Theorem 1.2, we improve the constant in Solovay’s
bound from three to two (ignoring logarithmic factors). Thus, we obtain the
following theorem.

######  Theorem 1.4.

There exists a constant $c$ such that for any $S\subset\mathbb{N}$, it holds
that $I(S)\leq 2\cdot H(S)+O(\log H(S))+c.$

To prove Theorem 1.3, we will introduce convenient terms. We will represent
the behavior of deterministic and randomized machines as the movement of cats
and ants on a directed graph.

##  2 Graph, Cats, Ants, Shadow Positions

###  2.1 Graph of Subsets of Natural Numbers

Let $G$ be a directed graph, with its vertices representing finite sets of
natural numbers, and edges leading from a set to all of its proper supersets.

###  2.2 Cats

We enumerate the inputs for $D$ in increasing order of their length (for
example: $\varepsilon$, 0, 1, 00, 01, 10, 11, 000, …). We associate a cat with
each input for $D$. Each cat simulates the actions of $D$ on the corresponding
input. At any given time, a cat is positioned in the vertex corresponding to
what $D$ has enumerated up to that point. At time zero, all cats are in the
$\varnothing$ vertex. As machine $D$ outputs new numbers, the cats move along
the edges of the graph to new positions. The cats are numbered in the same way
as the inputs they correspond to. Hence, $I(S)\leq k$ $\Leftrightarrow$ at
least one of the first $2^{k+1}-1$ cats enumerates the set $S$.

###  2.3 Ants

We model the behavior of machine $M$ on different inputs using the metaphor of
¡¡ants¿¿. While machine $M$ does not request random bits and only enumerates
numbers, we envision the movement of a unit-sized ant on the graph $G$. An ant
begins from an empty set and moves to corresponding sets as numbers appear in
the output (the ones already enumerated).

When the machine reaches the point of requesting a random bit, the ant splits
into two ¡¡children¿¿ — each of half the size. One follows the behavior of the
machine with a random bit $0,$ and the other follows the behavior with a
random bit $1,$ potentially moving differently. At some point, the ant may
need the next random bit, at which point it will split again into two, and so
on. At any moment in this modeling process, the ants are finite in number, and
each corresponds to a binary word (representing the random bits the ant
already knows). These cones form a partition of the Cantor space. Requesting a
random bit corresponds to dividing one of the cones in half.

Using this metaphor, we distinguish between an ¡¡ant¿¿ itself (a node in the
infinite tree) and its ¡¡position¿¿ in the graph. A node indicates which
random bits have been used in machine $M$’s computation, while a position
represents the set of numbers that have already appeared in machine $M$’s
output. There are two types of changes that occur during the modeling process:

  * •

The machine may request a random bit (in some computation path). Then, one ant
(corresponding to the bits of $x$ that are already requested) splits into two
(corresponding to nodes $x0$ and $x1$), inheriting the current position.

  * •

The machine (in some computation path) outputs a new number $m.$ The ant,
corresponding to the bits already requested, updates its position (moving to a
graph vertex obtained from the previous position by adding $m$).

In these terms, the mapping from the Cantor space to $\mathcal{P}(\mathbb{N})$
can be described as follows: for each point $w$ in the Cantor space, there is
a sequence of ants, each being the descendant of the previous one and
continuing its path on the graph. The combination of these paths enumerates a
set of natural numbers, which represents the image of the point $w.$ (It is
possible that only a finite number of bits from input $w$ will be used. In
this case, the last ant will not split further, and its path on the graph may
be either finite or infinite.)

###  2.4 Shadow Positions

In the description of the construction, in addition to the positions of the
ants on the graph, we use their shadow positions, which follow their actual
positions with some delay. Specifically, when an ant’s position changes, its
shadow position remains unchanged, except for specific explicitly highlighted
shifts. At the moment of such a shift, the shadow position of the ant moves to
its real position. When an ant splits, its children inherit not only its
position but also its shadow position. Then, the children may diverge, and
after shifts, their shadow positions may also diverge.

From this description, it’s evident that the shadow position of an ant is one
of its previous (real) positions, making it a subset of those positions. Each
ant can participate in several shifts (or none at all). For convenience, when
we later discuss the number of shifts in which a given ant participated, we
mean the total number of shifts for both the ant and its ancestors. (This
number will be important to us, particularly whether it is finite or
infinite.)

###  2.5 Shifts

The evolution and positions of ants are determined by the simulation of
machine $M$ and are not dependent on us. To describe the entire process, we
need to explain when and to which ants shifts are applied. The shift will
depend on a parameter $\varepsilon$ and a function $l(\varepsilon)$ based on
it. We will define the function $l(\varepsilon)$ and $\varepsilon$ later.

The conditions for a shift arise when there is a finite set $X$ for which
there are more than $\varepsilon$ ants whose positions are supersets of $X,$
and their shadow positions are subsets of $X.$ (The term ¡¡more¿¿ is
understood in terms of the cumulative ¡¡weight¿¿ of the ants - that is, the
measure of the corresponding set in the Cantor space.). More precisely,
initially, the shadow positions of these ants are temporarily set to be equal
to $X,$ and it is expected that one of the first $l(\varepsilon)$ cats will
enter* $X$ (the movement of cats is being simulated from the very beginning
until a cat enters the vertex $X$), after which the shadow positions are set
to be equal to the real ones.

Note*: It is possible that none of the first $l(\varepsilon)$ cats will ever
enter $X.$ However, we will choose $l(\varepsilon)$ in such a way that such a
cat will be found.

In case if there are several vertices $X$ where conditions for a shift exist,
any of them is chosen. Then (with new positions), it is checked whether there
is another vertex where the shift condition is met, and a shift is also
applied there, and so on, until there are no vertices where a shift is
possible. Then the simulation of machine $M$ and the corresponding processes
of ant movement and splitting are resumed.

Note: It is possible in principle that in the same vertex, after a shift is
performed, there are conditions for another shift (for example, the positions
of a large number of ants and their shadow positions were in $X,$ which made
the shift possible, but nothing changed after it). However, we do not perform
a second shift in the same vertex. (But we check all the others - whether
there are any other vertices where a shift is possible. Sooner or later, all
possible shifts will be exhausted since there is only a finite number of such
vertices where a shift is possible at the current simulation moment.)

###  2.6 Main Lemma

######  Lemma 2.1.

Let $S$ be a set with a probability of enumeration greater than $\varepsilon$
(the threshold from the shift conditions). Let $S^{\prime}\subset S$ be a
finite subset of it. Then at some point, a shift will occur for the set $X$
located between $S^{\prime}$ and $S$ (i.e., $S^{\prime}\subset X\subset S$).

Before proving Lemma 2.1, let’s show that it implies a desired bound for the
complexity of enumerating infinite sets. Consider an increasing sequence of
finite sets $S^{\prime}$ converging to $S$ and apply Lemma 2.1 to each of
them, obtaining, for each, its set $X$ (and one of the first $l(\varepsilon)$
cats servicing this set). Since there is a finite number of cats, one of them
must have participated in servicing an infinite number of sets $S^{\prime}$,
never leaving $S$ and being in the supersets of infinitely many sets
$S^{\prime}$. Therefore, it will eventually enumerate $S$. Thus, we have:

$I(S)\leq\log_{2}l(\varepsilon)$

Now we will show how to use this to prove Theorem 1.3.

Proof of Theorem 1.3. Let $k$ be an integer. We will show that if we set
$\varepsilon=2^{-k}$ and $l(\varepsilon)=2^{\alpha k+O(\log k)}$, then during
a shift, there will always be a cat among the first $l(\varepsilon)$ that
comes to $X.$ Using $I(S)\leq\log_{2}l(\varepsilon),$ we will prove Theorem
1.3.

Consider a randomized machine $M^{\prime}$ that models the movement of the
shadow positions of ants. To do this, $M^{\prime}$ needs to know
$\varepsilon,$ so $M^{\prime}$ uses the first $2\lceil\log_{2}k\rceil+2$ of
its bits to determine $k$ and then compute $\varepsilon=2^{-k}.$ Thus, if at
some point, a set $X$ has at least $2^{-k}$ shadow ants concentrated in it,
then $M^{\prime}$ will have a probability of being in this set of at least
$\varepsilon^{\prime}=2^{-k-2\log_{2}k-3}$. However,

$\alpha\log_{2}1/\varepsilon^{\prime}+O(\log_{2}\log_{2}1/\varepsilon^{\prime})=\alpha
k+O(\log_{2}k)$

Therefore, we can choose $l(\varepsilon)$ such that any set enumerated by
$M^{\prime}$ with high probability will be enumerated by one of the first
$l(\varepsilon)$ cats. In other words, during a shift, there will always be a
cat that comes to $X.$

$\square$

Now, it only remains to prove Lemma 2.1.

##  3 Proof of Lemma 2.1

###  3.1 Number of Shifts

At every moment $t$ of the process, the Cantor space is divided into cones
corresponding to ants. For each ant, we can count the total number of shifts
in which it (itself or its ancestors) participated. We can define the set
$W_{k}^{t}$ as the set in the Cantor space corresponding to ants with $k$ or
more shifts by the time $t$. This is a basic (open and closed) set; the larger
$k$ is, the smaller $W_{k}^{t}$ (for a given $t$). On the other hand,
$W_{k}^{t}$ grows with increasing $t$. We can take the union over all $t$ and
obtain an open set $W_{k}$ (it is even effectively open since the process is
algorithmic — we assume that $\varepsilon$ is rational). We obtain a
decreasing sequence of open sets:

$W_{1}\supset W_{2}\supset W_{3}\supset\ldots\supset W_{k}\supset\ldots$

in the Cantor space. Membership in the sequence $w$ to the set $W_{k}$ means
that in the chain of ants corresponding to shifts in the direction of the bits
of $w$, there were at least $k$ shifts (in total, for all participants). This
chain can be finite or infinite (the same ant, without splitting, can
participate in several shifts, or even an infinite number of them).

Now, we can consider the set $W_{\infty}=\bigcap_{k}W_{k}$. It consists of
those sequences where the corresponding chain of ants is involved in an
infinite number of shifts.

###  3.2 The Case of Non-empty Intersection

In addition to $W_{\infty}$, consider the set $U$ in the Cantor space,
consisting of those sequences for which the probabilistic machine $M$
enumerates the set $S$. Do the sets $U$ and $W_{\infty}$ intersect? We will
show that if they do intersect, then the statement of Lemma 2.1 is true, and
then we will contradict the assumption that the intersection is empty.

Let’s assume that the intersection is not empty, and $w$ is a sequence
belonging to both $U$ and $W_{\infty}$. Then, with the bits from $w$, the
machine $M$ enumerates $S$, and the corresponding $w$ ants are involved in an
infinite number of shifts. Since the machine $M$ enumerates $S$, all the
positions of these ants will be subsets of $S$. Furthermore, for our finite
set $S^{\prime}$, there will be a moment when the position of the ant becomes
a superset of $S^{\prime}$. This is also true for the shadow position in one
of the following moments, because with each shift (and there are infinitely
many of them), the shadow position catches up with the real position. After
this, another shift will occur, and the set $X$ for this shift will contain
$S^{\prime}$ (because it contains the current shadow position) and will be
contained in $S$ (because it is contained in the real position of the same
ant).

###  3.3 The Case of Empty Intersection

We must lead to a contradiction the assumption that the intersection of the
sets $U$ (sequences where the machine enumerates $S$) and
$W_{\infty}=\cap_{k}W_{k}$ is empty. (Note that we can forget about
$S^{\prime}$ at this point.) Let’s assume that it is. Then, the sets $U\cap
W_{k}$ decrease and have an empty intersection. Therefore, their measures tend
to zero, and we can find such an $N$ that the measure of the intersection
$U\cap W_{N}$ is very small (less than some $\delta$, which we will choose
later and which will be less than the excess of the measure of $U$ above the
threshold $\varepsilon$). Choose and fix such $N$.

The set $W_{N}$ is open and is a union of an increasing sequence of sets
$W_{N}^{t}$. For a sufficiently large $T$, the difference between the measures
of $W_{N}$ and $W_{N}^{T}$ can be made arbitrarily small. Recall that for a
given $t$, the set $W_{N}^{t}$ consists of cones (in the Cantor space) over
ants (vertices of a binary tree) that have already undergone $N$ shifts by
time $t$. The rest of the ants with their cones form the complement to the set
$W_{N}^{t}$. Division of ants does not change these sets, but as time
increases, there will be shifts with these ants or their descendants, and then
some part of the complement to $W_{N}^{t}$ will move to $W_{N}^{t}$. We want
this process to be almost complete by the time of $T$. Moreover, we want
similar processes for all sets $W_{1},\ldots,W_{N}$ to be almost complete as
well. We will require that the difference between the measures of $W_{n}$ and
$W_{n}^{T}$ is less than $\delta/N$ for all $n=1,2,\ldots,N$. (Since $N$ is
fixed before choosing $T$, this is possible.) This means that the total
measure of the ants that will undergo their $1$st, $2$nd, …, $(N-1)$th shift
after time $T$ (either themselves or their descendants) is not greater than
$N\cdot(\delta/N)=\delta$.

So, consider all ants that have undergone fewer than $N$ shifts by time $T$.
What proportion of their continuations is made up of sequences from $U$ (which
lead to the enumeration of $S$)? By construction, $U$ barely intersected with
$W_{N}$ (less than $\delta$), and the intersection with $W_{N}^{T}$ will be
even smaller. Therefore, the measure we are interested in will be no less than
$P(U)-\delta$. Let’s look at the positions of these ants. Some of them have
exited $S$ (they are not subsets of $S$), and such ants do not contribute to
$S$. Therefore, if we discard them, we will be left with a finite set of ants
for which:

  * •

their current positions are subsets of $S$ (and this is also true for their
shadow positions).

  * •

the measure of their continuations that are in $U$ is not less than
$P(U)-\delta$.

  * •

the measure of them and their descendants who will undergo a shift is not more
than $\delta$.

Let $X$ be a finite subset of $S$, which is a union of all shadow positions of
ants from this set. All points in $U$ enumerate $S$, so for the corresponding
ants, their position will eventually become a superset of $X$. Applying
measure continuity again, we conclude that the measure of the ants whose
position will become a superset of $X$ at some point will be no less than
$P(U)-2\delta$. For some of these ants, their shadow position may have
changed, but the measure of such ants will not be greater than $\delta$. So if
$P(U)-3\delta>\varepsilon$, conditions for a shift with the set $X$ will be
created at some point. Therefore, the measure of the ants that have undergone
a shift will be greater than $\varepsilon$, and we can assume without loss of
generality that $\delta<\varepsilon$. This will result in a contradiction.

Thus, the case of an empty intersection is impossible.

##  4 Discussion

One of the most natural questions in theoretical computer science is how much
more efficient randomized computations are compared to deterministic ones. As
Theorem 1.3 demonstrates, randomized computations are not superior to
deterministic ones when considering infinite sets instead of finite ones.
Moreover, the gap between complexities can be reduced to a factor of 2 (modulo
logarithmic factors). To prove Theorem 1.3, we utilized a trick first used by
Solovay: instead of cats (the deterministic machine) trying to catch the
actual positions of ants (the randomized machine), the cats catch the shadow
positions of the ants, which are slightly modified real positions. In
Solovay’s method, managing shadow positions required transmitting additional
$H(S)$ bits of information. We were able to reduce the number of additional
bits to $O(\log H(S))$ and, thereby, improve the upper bound.

Can we reduce the upper bound even more or find a matching lower bound? In
[5], Vereshchagin used Martin’s game to obtain an upper bound for finite sets.
However, Ageev [1] proved that the quadratic bound is both a lower and upper
bound in Martin’s game. Thus, to improve the upper bound further, a novel
technique must be developed. It is also unknown if the lower bound in Martin’s
game does extend to a lower bound of deterministic complexity.

##  5 Acknowledgements

We extend our gratitude to Nikolay Vereshchagin, Alexander Shen, and Daniil
Musatov for their invaluable assistance in both validating our findings and
contributing to the writing of this article.

## References

  * [1] M. Ageev.  Martin’s game: a lower bound for the number of sets.  Theoretical Computer Science, 289(1):871–876, 2002.
  * [2] K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro.  Computability by probabilistic machines.  In C. E. Shannon and J. McCarthey, editors, Automata Studies, pages 183–212. Princeton University Press, Princeton, NJ, 1956.
  * [3] D. A. Martin.  Borel indeterminacy.  Annals of Mathematics, 102:363–371, 1978.
  * [4] R. M. Solovay.  On random r.e. sets.  In R. Chaqui A.I. Arruda, N.C.A. da Costa, editor, Non-Classical Logics, Model Theory and Computability, pages 283–307. North-Holland, Amsterdam, 1977.
  * [5] N. K. Vereshchagin.  Kolmogorov complexity of enumerating finite sets.  Inform. Process. Lett., 103(1):34–39, 2007.