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.