Proof that DIGICOMP_EXP is in CC·#L

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 \mathsf {CC}. 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 \mathsf{PL} (and the same proof can be extended to show that it’s hard for \mathsf {CC} \cdot \mathsf {PL}, by following the simulation of \mathsf {PL} in DIGICOMPEXP by an arbitrary \mathsf {CC} circuit). I then follow up with a proof that DIGICOMPEXP is in \mathsf {CC} \cdot \# \mathsf {L}. 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 \mathsf {CC} \cdot \# \mathsf {L}, hoping that it will be comprehensible this time.

On a side note, I want to remark that although \mathsf {CC} 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 \mathsf {CC} through a mechanism that does not obviously extend to all of \mathsf {P}. 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 X, Y, Z denote nodes in the computational graph of the pebbles model. We denote that X splits into Y and Z by writing X \to (Y, Z), and that X and Y merge into Z by (X, Y) \to Z. Let C be the function that maps a node to how many pebbles pass through it in the DIGICOMPEXP computation. Then C is some suitable (exponentially large) constant in the starting node. Given a split X \to (Y, Z), we have C (Y) = \lceil X/2 \rceil and C (Z) = \lfloor X/2 \rfloor. Given a merge (X, Y) \to Z, we have C (Z) = C (X) + C (Y).

Now define another function W mapping nodes to dyadic rationals as follows: W maps the starting node to the same value as C. At a merge (X, Y) \to Z we have W (Z) = W (X) + W (Y) like with C. Finally, at a split X \to (Y, Z) we have W (Y) = W (Z) = W (X)/2. In words, W is like C except that a splitter always splits the pebbles evenly between the two piles, even if this leads to fractional pebbles.

Observe that W (X) can be expressed as a weighted count of the number of paths from the starting node to X, weighted by the 2 to the power of negative the number of splitters in each path. It follows that the binary digits of W are computable in \# \mathsf {L}. Next, I will show that C is \mathsf {CC}-computable in terms of W, and therefore DIGICOMPEXP is in \mathsf {CC} \cdot \# \mathsf {L}.

Define R (X) = C (X) - \lfloor W (X) \rfloor. Then R is 0 at the starting node. I will study how R behaves in the operations of splits and merges:

Consider a split X \to (Y, Z). Let c = \lfloor W (X) \rfloor \mod 2 be the binary units digit of W (X). Then

\lfloor W (X) \rfloor = 2 \left\lfloor \frac {\lfloor W (X) \rfloor} {2} \right\rfloor + c = 2 \lfloor W (X) / 2 \rfloor + c

It follows that

C (Y) = \left\lceil \frac {\lfloor W (X) \rfloor + R (X)} {2} \right\rceil = \left\lceil \lfloor W (X)/2 \rfloor + \frac {R (X) + c} {2} \right\rceil = \lfloor W (Y) \rfloor + \left\lceil \frac {R (X) + c} {2} \right\rceil

and so R (Y) = \lceil (R (X) + c)/2 \rceil. By a similar argument we have R (Z) = \lfloor (R (X) + c)/2 \rfloor.

Next, consider a merge (X, Y) \to Z. Observe that \lfloor W (Z) \rfloor = \lfloor W (X) + W (Y) \rfloor = \lfloor W (X) \rfloor + \lfloor W (Y) \rfloor + \lfloor \{W (X)\} + \{W (Y)\} \rfloor. Since C (Z) = C (X) + C (Y), it follows that R (Z) = R (X) + R (Y) - \lfloor \{W (X)\} + \{W (Y)\} \rfloor. Note that \lfloor \{W (X)\} + \{W (Y)\} \rfloor is the unit digit of the sum of the fractional parts of W (X) and W (Y), and so is \mathsf {CC}-computable in terms of W because binary addition is \mathsf {CC}-computable.

In conclusion, it is possible to compute the R value of an arbitrary node using the operations R \mapsto (\lceil R/2 \rceil, \lfloor R/2 \rfloor), (R_0, R_1) \mapsto R_0+R_1 and R \mapsto R+c where c is a small integer that’s \mathsf{CC}-computable given the values of W, and this computation does not need any fanout. Moreover, R (X) 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 x in an integral pebble pile by x+N in an ordinary pebble pile where N is an even number large enough to guarantee that x+N is nonnegative. Then the splitting and merging operations on x are represented by the same operations on x+N, followed by adding or subtracting an appropriate constant. Finally, the output of the DIGICOMPEXP computation is given by whether C (Z) = \lfloor W (Z) \rfloor + R (Z) is positive for some terminal node Z, which is \mathsf {CC}-computable in terms of the binary digits of W (Z) and R (Z) + N in unary.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s