Take the 2-minute tour ×
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.

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|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

1 Answer 1

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|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

 
discard

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.