Einheitliche Derandomisierung von Schaltungskomplexitätsklassen

Sei eine Komplexitätsklasse und BP- C das randomisierte Gegenstück von C, das auf die gleiche Weise definiert ist , wie BPP in Bezug auf P definiert ist . Formal stellen wir polynomiell viele zufällige Bits bereit und akzeptieren eine Eingabe, wenn die Wahrscheinlichkeit zu akzeptieren über $\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{BPP}$$\textrm{P}$ .$\frac{2}{3}$

In einem früheren Beitrag habe ich gefragt, ob bekannt ist, ob die Gleichheit zwischen und BP- C für C eine Schaltungskomplexitätsklasse ist. Die Antwort lautet Ja für alle Komplexitätsklassen, die aussagekräftig genug sind, um die Mehrheit zu berechnen, und für AC 0 aus einem anderen Grund. Diese Ergebnisse sind jedoch uneinheitlich und ich würde gerne wissen:$\mathcal{C}$$\textrm{BP-}\mathcal{C}$$\mathcal{C}$$\textrm{AC}^0$

1. Sind einheitliche Versionen dieser Ergebnisse untersucht oder bekannt? Teilergebnisse?

2. Bedeuten sie langjährige Vermutungen?

Ich glaube, dass eine einheitliche Derandomisierung von genau P = BPP ist, daher erwarte ich, dass die Antwort "Ja" lautet, aber mir ist weniger klar, was eine einheitliche Derandomisierung kleiner Klassen innerhalb der NC- Hierarchie bedeuten würde.$\textrm{P}/\textrm{poly}$$\textrm{P}=\textrm{BPP}$$\textrm{NC}$

Die Klasse Uniform-RNC wurde viel untersucht. Es ist ein offenes Problem, ob Uniform-RNC = Uniform-NC. Uniform- (R) NC entsprechen (randomisierten) PRAMs mit polynomiell vielen Prozessoren und polylogarithmischer Laufzeit (siehe das Handbuch der Theoretischen Informatik, Band A). Die Frage ist also, ob jeder effiziente randomisierte parallele Algorithmus derandomisiert werden kann.

Da symbolische Determinantenidentitätstests in Uniform-RNC durchgeführt werden, impliziert die Derandomisierung von RNC Schaltungsuntergrenzen durch die Ergebnisse von Kabanets & Impagliazzo (Computational Complexity, 13 (1-2), Seiten 1-46, 2004).

Ein wichtiger Sonderfall ist die Frage, ob wir in Uniform-NC perfekte Übereinstimmungen berechnen können. Es sind mehrere randomisierte parallele Algorithmen bekannt, aber wir wissen nicht, ob es einen deterministischen gibt. Kürzlich haben Fenner, Gurjar und Thierauf (STOC 2016) gezeigt, dass wir durch gleichmäßige Schaltungen mit polylogarithmischer Tiefe und Quasipolynomgröße perfekte Übereinstimmungen in zweigeteilten Graphen berechnen können.