<p>They are the same: BPNC = DBPNC.</p>

<p>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:</p>

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

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

<ol>
<li>Sort the new indices.</li>
<li>Merge the lists of old and new indices (e.g., with <a href="http://epubs.siam.org/doi/abs/10.1137/0217049" rel="nofollow">Cole 1988</a>).</li>
<li>Scatter appropriately.</li>
</ol>

CC BY-SA 3.0
2013-01-13T04:23:02.980Z
Oops, the last step is a bit flawed.  Will (hopefully) fix shortly.
Geoffrey Irving
CC BY-SA 3.0
2013-01-13T04:35:16.523Z
Should be fixed now.
Geoffrey Irving
CC BY-SA 3.0
2013-01-12T20:44:31.430Z
2013-01-13T04:34:57.880Z
2013-01-13T04:34:57.880Z
Geoffrey Irving
<p>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.</p>

<p>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.</p>

<p>Do we know whether BPNC = DBPNC?</p>

CC BY-SA 3.0
2013-01-11T17:08:15.913Z
If no one knows the answer, does anyone know if there are existing names for either of these complexity classes?
Geoffrey Irving
<cc.complexity-theory><complexity-classes><dc.parallel-comp><randomness><pseudorandomness>
Is deterministic pseudorandomness possibly stronger than randomness in parallel?
Geoffrey Irving
# Is deterministic pseudorandomness possibly stronger than randomness in parallel?

(Asked by: username_0 on 2013-01-07)

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?

**Tags:** cc.complexity-theory, complexity-classes, dc.parallel-comp, randomness, pseudorandomness

> **Comments:**
> **username_0**: If no one knows the answer, does anyone know if there are existing names for either of these complexity classes?  

---

## 1 answers

### Answer by username_0 on 2013-01-12. Score: 4 | Accepted answer

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](http://epubs.siam.org/doi/abs/10.1137/0217049)).
3. Scatter appropriately.

> **Comments:**
> **username_0**: Oops, the last step is a bit flawed.  Will (hopefully) fix shortly.  
> **username_0**: Should be fixed now.  

---

