Czy pseudolosowość deterministyczna jest prawdopodobnie silniejsza niż przypadkowość równolegle?

Niech klasa BPNC (kombinacja i ) będzie algorytmami równoległymi głębokości dziennika z ograniczonym prawdopodobieństwem błędu i dostępem do losowego źródła (nie jestem pewien, czy to ma inną nazwę). Podobnie zdefiniuj klasę DBPNC, z tym wyjątkiem, że wszystkie procesy mają losowy dostęp do losowego strumienia bitów ustalonego przy uruchomieniu algorytmu.N $\mathsf{BPP}$$\mathsf{NC}$

Innymi słowy, każdy proces w BPNC ma dostęp do odrębnego losowego źródła, podczas gdy algorytmy DBPNC mają wspólny generator idealnie losowego licznika.

Czy wiemy, czy BPNC = DBPNC?

Są takie same: BPNC = DBPNC.

Powiedzmy, że maszyna BPNC jest podawana jako dane wejściowe programu DBPNC do symulacji. Uruchom program w kroku blokady. Najpierw załóżmy, że wskaźniki pomiędzy poszczególnymi krokami są różne, więc nie musimy pamiętać starych losowych bitów. Na każdym etapie każdy procesor prosi o losowy bit o określonym indeksie do udostępnionego strumienia. Oblicz i rozprowadź losowe bity w następujący sposób:

1. Posortuj wskaźniki wśród procesorów i zapamiętaj pochodzenie każdego bitu.
2. Koordynuj między sąsiednimi procesorami, aby obliczyć zakresy identycznych wskaźników.
3. Obliczyć każdy losowy bit na pierwszym procesorze, który jest jego właścicielem po sortowaniu.
4. Rozrzut w identycznych zakresach.
5. Odeślij z powrotem do procesu źródłowego (w razie potrzeby poprzez odwrócenie algorytmu sortowania).

Aby umożliwić procesorom zapytanie o stare indeksy, niech każdy procesor zapamięta (wyniki) wszystkich poprzednich epok sortowania. Aby sprawdzić, czy nowo żądane indeksy wystąpiły w danej poprzedniej epoce, wykonaj następujące czynności:

1. Sortuj nowe indeksy.
2. Scal listy starych i nowych indeksów (np. Z Cole 1988 ).
3. Rozprowadź odpowiednio.