July | 2017 | What Immanuel Kant teach you

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 DIGICOMP_EXP 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 DIGICOMP_EXP 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 DIGICOMP_EXP by an arbitrary $\mathsf {CC}$ circuit). I then follow up with a proof that DIGICOMP_EXP 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 DIGICOMP_EXP 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 DIGICOMP_EXP 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 DIGICOMP_EXP 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 DIGICOMP_EXP 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.

What Immanuel Kant teach you

Some random dude's thoughts

Monthly Archives: July 2017

Proof that DIGICOMP_EXP is in CC·#L