Three years ago, Scott Aaronson wrote the “paperlet” in blog title The Power of the Digi-Comp II: My First Conscious Paperlet. In it, he studies models of computation based on the mechanical computer Digi-Comp II, which employs balls rolling down switches and toggles. Using the so-called “pebbles model”, he shows that a natural generalization of Digi-Comp II to an arbitrary pattern of switches is equivalent in computational power to a complexity class called . He also proposes a problem DIGICOMPEXP which represents simulating Digi-Comp II with a polynomially large network and an exponentially large number of pebbles, and poses the question of what is this problem’s computational complexity.
In the comments, I offer a proof that DIGICOMPEXP is hard for (and the same proof can be extended to show that it’s hard for
, by following the simulation of
in DIGICOMPEXP by an arbitrary
circuit). I then follow up with a proof that DIGICOMPEXP is in
. Although Aaronson was impressed by my first result, he was unable to follow and was unconvinced by my second result. I don’t blame him — at the time, I had difficulties with writing and specifically with explaining my mathematical thinking. Now that I have gotten better at writing and specifically I have much more experience with writing university-level problem sets in mathematics, I want to rewrite my second proof showing that DIGICOMPEXP is in
, hoping that it will be comprehensible this time.
On a side note, I want to remark that although is a fairly obscure complexity class, Aaronson’s post was not my first exposure to the class, and my previous exposure was also in the context of a recreational mathematics problem: In the sandbox computer game Dwarf Fortress many players have built computers within the gameworld. It turns out that the amount of computation that is possible in a single timestep contains
through a mechanism that does not obviously extend to all of
. For details, see my forum post here and my Stack Exchange question here.
Now, the proof:
In the following, I’m letting the variable names denote nodes in the computational graph of the pebbles model. We denote that
splits into
and
by writing
, and that
and
merge into
by
. Let
be the function that maps a node to how many pebbles pass through it in the DIGICOMPEXP computation. Then
is some suitable (exponentially large) constant in the starting node. Given a split
, we have
and
. Given a merge
, we have
.
Now define another function mapping nodes to dyadic rationals as follows:
maps the starting node to the same value as
. At a merge
we have
like with
. Finally, at a split
we have
. In words,
is like
except that a splitter always splits the pebbles evenly between the two piles, even if this leads to fractional pebbles.
Observe that can be expressed as a weighted count of the number of paths from the starting node to
, weighted by the 2 to the power of negative the number of splitters in each path. It follows that the binary digits of
are computable in
. Next, I will show that
is
-computable in terms of
, and therefore DIGICOMPEXP is in
.
Define . Then
is 0 at the starting node. I will study how
behaves in the operations of splits and merges:
Consider a split . Let
be the binary units digit of
. Then
It follows that
and so . By a similar argument we have
.
Next, consider a merge . Observe that
. Since
, it follows that
. Note that
is the unit digit of the sum of the fractional parts of
and
, and so is
-computable in terms of
because binary addition is
-computable.
In conclusion, it is possible to compute the value of an arbitrary node using the operations
,
and
where
is a small integer that’s
-computable given the values of
, and this computation does not need any fanout. Moreover,
has a polynomial bound. This is like the pebbles model, except that the number of pebbles may be negative. This integral pebbles model may be emulated by the ordinary pebbles model by representing a possibly negative amount
in an integral pebble pile by
in an ordinary pebble pile where
is an even number large enough to guarantee that
is nonnegative. Then the splitting and merging operations on
are represented by the same operations on
, followed by adding or subtracting an appropriate constant. Finally, the output of the DIGICOMPEXP computation is given by whether
is positive for some terminal node
, which is
-computable in terms of the binary digits of
and
in unary.