Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let the class BPNC (the combination of $\mathsf{BPP}$ and $\mathsf{NC}$) be log depth parallel algorithms with bounded error probability and access to a random source (I'm not sure if this has a different name). Define the class DBPNC similarly, except that all processes have random access into a random stream of bits fixed at algorithm startup.

In other words, each process in BPNC has access to a distinct random source, while DBPNC algorithms have a shared perfectly random counter mode generator.

Do we know whether BPNC = DBPNC?

share|cite|improve this question
If no one knows the answer, does anyone know if there are existing names for either of these complexity classes? – Geoffrey Irving Jan 11 '13 at 17:08
up vote 4 down vote accepted

They are the same: BPNC = DBPNC.

Say a BPNC machine is given as input a DBPNC program to simulate. Execute the program in lock step. First assume that the indices between different steps are distinct, so that we do not need to remember old random bits. At each step, each processor asks for a random bit at a specific index into the shared stream. Compute and distribute the random bits as follows:

  1. Sort the indices among the processors and remember the origin of each bit.
  2. Coordinate among adjacent processors to compute the ranges of identical indices.
  3. Compute each random bit on the first processor that owns it after sorting.
  4. Scatter throughout the identical ranges.
  5. Send back to the origin process (if necessary by reversing the sorting algorithm).

To allow processors to ask for old indices, have each processor remember the (results) of all previous sorting epochs. To check whether newly requested indices occurred in a given previous epoch, do

  1. Sort the new indices.
  2. Merge the lists of old and new indices (e.g., with Cole 1988).
  3. Scatter appropriately.
share|cite|improve this answer
Oops, the last step is a bit flawed. Will (hopefully) fix shortly. – Geoffrey Irving Jan 13 '13 at 4:23
Should be fixed now. – Geoffrey Irving Jan 13 '13 at 4:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.