Jednolita derandomizacja klas złożoności obwodów

Pozwolić $\mathcal{C}$ być klasą złożoności i $\textrm{BP-}\mathcal{C}$ być randomizowanym odpowiednikiem $\mathcal{C}$ zdefiniowane w taki sam sposób jak $\textrm{BPP}$ jest zdefiniowany w odniesieniu do $\textrm{P}$. Bardziej formalnie zapewniamy wielomianowo wiele losowych bitów i akceptujemy dane wejściowe, jeśli prawdopodobieństwo, że zostanie zaakceptowane, jest zakończone$\frac{2}{3}$.

W poprzednim poście zapytałem, czy wiadomo, czy równość się utrzymuje $\mathcal{C}$ i $\textrm{BP-}\mathcal{C}$ dla $\mathcal{C}$klasa złożoności obwodu. Odpowiedź brzmi: tak dla wszystkich klas złożoności wystarczająco ekspresyjnych, aby obliczyć Większość i dla$\textrm{AC}^0$z innego powodu. Te wyniki są jednak niejednolite i chciałbym wiedzieć:

1. Czy jednolite wersje tych wyników są badane lub znane? Jakieś częściowe wyniki?

2. Czy implikują długotrwałą hipotezę?

Uważam, że jednolita derandomizacja $\textrm{P}/\textrm{poly}$ jest dokładnie $\textrm{P}=\textrm{BPP}$ więc oczekuję, że odpowiedź brzmi „tak”, ale dla mnie mniej jasne jest, jakie jednolite derandomizacja małych klas w obrębie $\textrm{NC}$-hierarchia implikuje.

Mundur klasowy - RNC był często badany. Problemem otwartym jest, czy uniform-RNC = uniform-NC. Uniform- (R) NC odpowiada (randomizowanym) PRAM z wielomianowo wieloma procesorami i polilogarytmicznym czasem pracy (patrz Handbook of Theoretical Computer Science Vol. A). Pytanie brzmi zatem, czy każdy skuteczny randomizowany równoległy algorytm może zostać zdesandomizowany.

Ponieważ testy tożsamości symbolicznej determinant są w jednolitym RNC, derandomizacja RNC implikuje dolne granice obwodu przez wyniki Kabanetsa i Impagliazza (Computational Complexity, 13 (1-2), strony 1-46, 2004).

Ważnym szczególnym przypadkiem jest pytanie, czy możemy obliczyć idealne dopasowania w uniform-NC. Znanych jest kilka losowych algorytmów równoległych, ale nie wiemy, czy istnieje jeden deterministyczny. Ostatnio Fenner, Gurjar i Thierauf (STOC 2016) wykazali, że możemy obliczyć idealne dopasowania na grafach dwudzielnych za pomocą jednolitych obwodów o głębokości polilogarytmicznej i wielkości quasipolynomialnej.