Before I respond to your questions I want to take a chance to improve my own terminology. My simplification of DIGICOMP with rational numbers as pebble values was called in #43 “the simplified model”; I will instead call it “the rational approximation”. The floor of the rational approximation, which I previously called an “approximation”, will be called “the integer approximation”.

the number of balls that needs to be added or removed can be calculated in CC^#L.

Can you be more explicit about this step? How do we do the calculation in CC#L? (What do we use the CC part for, and when does CC call the #L oracle?)

The important point about the rational approximation and the integer approximation is that they are both derived from a #L computation in a very simple manner. In turn, the number of balls that need to be added or removed is derived in relatively simple way from the value of the rational approximation, which is why it’s in #L. To be more precise, for merging piles it is necessary to compute frac(x)+frac(y) where x and y are the rational approximations of two piles. x and y are both of the form a/2^n for a in #L. Taking the fractional part of a/2^n is just taking away a certain number of digits from the left, and addition is in CC. Splitting is even easier; it requires taking the parity of floor(a/2^n), which is just the n’th digit from the right (counting from zero).

Also, I didn’t understand the part about anti-pebbles. I don’t understand why, once we have the above, we aren’t already done;

What we achieved so far is that we found a machine which follows the real rules of DIGICOMP but involves small known perturbations at each gate, and ends up with a result whose value we know. What we want to achieve is to figure out the output value for the DIGICOMP machine which doesn’t have any perturbations. In the case where the only perturbations are the removal of balls, getting one from the other is fairly easy. You can just place back all the balls that were removed earlier, taking advantage of the fact that DIGICOMP is invariant under changing the order of the balls. In a sense the balls are not actually removed, but merely delayed, and the result is the same as DIGICOMP computation without perturbations. In the case where balls are added as well a similar idea works, but requires the usage of anti-pebbles.

In the pebbles model, allowing anti-pebbles is equivalent to letting the number of pebbles be an arbitrary integer, just the way you guessed, and the pebble operations remain the same. I use this to show that DIGICOMP with anti-pebbles is in CC. However, I want to take advantage of order-independence, which is a property of the original DIGICOMP model and is harder to formulate in the pebbles model. That is why I invoked anti-pebbles and added them to the original DIGICOMP model. In retrospect it would have made more sense to call them “anti-balls”, to more clearly distinguish balls in the DIGICOMP model and pebbles in the pebbles model. The key property of anti-balls is that placing a ball a certain place and then placing an anti-ball does not change the state of the machine

By the way, I made a mistake when I originally described anti-balls. I stated that “anti-pebbles move like ordinary pebbles”, but actually, when an anti-ball goes through a splitter, it goes the *opposite* direction from where an ordinary ball would go (and also changes the state of the splitter like an ordinary ball). This might have been the cause of your confusion.

Finally,I want to point out that this argument actually gives a slightly stronger bound for DIGICOMP_EXP. This is because the calls to #L are only necessary for computing the rational approximation, and the parameters for this come directly from the input without any CC computation. I believe the name for the complexity class of this type of calculation is $latex \mathsf{CC} \cdot \sharp \mathsf{P}$. Similarly, my lower bound of PL can easily be improved to $latex \mathsf{CC} \cdot \mathsf{PL}$ by postprocessing the output of my PL circuit. Together these give a fairly tight constraint.

]]>Thanks; that’s extremely interesting! I’m sorry for the delay; only today did I have time to work through your proof. Alas, there are still a few points that I don’t understand.

- the number of balls that needs to be added or removed can be calculated in CC^#L.

Can you be more explicit about this step? How do we do the calculation in CC^{#L}? (What do we use the CC part for, and when does CC call the #L oracle?)

Also, I didn’t understand the part about anti-pebbles. I don’t understand why, once we have the above, we aren’t already done; I don’t understand why anti-pebbles solve the problem; and I don’t understand what the exact rules are governing the evolution of anti-pebbles. Do “anti-pebbles” just mean that the number of pebbles in a given pile is allowed to be an arbitrary integer, rather than a nonnegative one? But it’s still the case that merging a pile with x pebbles with a pile with y pebbles yields a pile with x+y pebbles, and that splitting a pile with x piles yields piles with floor(x/2) and ceiling(x/2) pebbles?

]]>Consider a simplified pebbles model where the amount of pebbles at a point may be rational numbers, and splitters turn a pile of x pebbles into two piles of x/2. Then the number of pebbles in any given point is always of the form n/2^l, where l is independent of the input and n is in #L. Consider the approximation which says that the number of pebbles at point is the floor of the value given by the simplified pebbles model. The true pebbles model differs from this approximation as follows:

* When two piles merge and the simplified pebble model gives them values x and y, this approximation says that the output value is floor(x+y). The value it should receive is floor(x)+floor(y), which is one less if frac(x)+frac(y) is greater than or equal to 1, and otherwise the same.

* When the simplified pebble model gives a value of x at a point which is followed by a split, this approximation says a pile of size floor(x) splits into two piles of size floor(x/2)=floor(floor(x)/2). However, one of the piles would be ceiling(floor(x)/2) in the true model, which is one pebble more if floor(x) is odd, and otherwise the same. For reasons that will be clear later, a better way to think of it is that in the simplified pebble model one pebble is removed from a pile before it splits if it is odd. Then the number of pebbles going through a splitter is always even.

In short, it is possible to obtain this approximation by taking an actual DIGICOMP_EXP computation and adding or removing at most one ball next to each gate, and the number of balls that needs to be added or removed can be calculated in CC^#L.

It seems like it should be possible to use order-independence of the pebble model to then calculate the actual DIGICOMP_EXP computation out of the simplified version. However, to make this work it is necessary to make use of anti-pebbles. Anti-pebbles move like ordinary pebbles, but when they merge with an ordinary pebble they are both destroyed. DIGICOMP with anti-pebbles is still order-independent, and allows you to ‘reverse’ a placement of a pebble of one sign by placing another pebble of the opposite sign. By starting with the simplified model and then placing pebbles of appropiate sign in the right places it is indeed possible to simulate DIGICOMP_EXP with polynomially many pebbles. Note that because in the simplified model an even number of pebbles always goes through a splitter it is not necessary to figure out the state of the splitters after the simplified model is execeuted.

Now the remaining task it to simulate DIGICOMP with polynomial pebbles but that some of them are anti-pebbles. This is equivalent to the pebble model where the number of pebbles is an arbitrary integer. However, a pile of size z can be represented as a pile of size n+z where n is an appropiately large even number. To split z, split n+z into n/2+floor(z/2) and n/2+ceiling(z/2) and add n/2 pebbles to each of these. To merge z and w, merge n+z and n+w into 2*n+z+w. Afterwards it is possible to use a pebbles circuit to subtract n from this, or alternately, in the model you made to show that pebbles is in CC it is possible to subtract n directly.

]]>