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?

  • $\begingroup$ If no one knows the answer, does anyone know if there are existing names for either of these complexity classes? $\endgroup$ Jan 11, 2013 at 17:08

1 Answer 1


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.
  • $\begingroup$ Oops, the last step is a bit flawed. Will (hopefully) fix shortly. $\endgroup$ Jan 13, 2013 at 4:23
  • $\begingroup$ Should be fixed now. $\endgroup$ Jan 13, 2013 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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