Le RNC uniforme est-il contenu dans l'espace du polylogue?

NC-Log-space-uniform est contenu dans un espace polylogue déterministe (parfois écrit PolyL). Le RNC à espace de log uniforme est-il également dans cette classe? La version standard randomisée de PolyL devrait être en PolyL, mais je ne vois pas que RNC (uniforme) est en randomL-PolyL.

La difficulté que je vois est qu'en RNC, le circuit peut "regarder les bits aléatoires" autant qu'il le souhaite; c'est-à-dire que les entrées aléatoires peuvent avoir un fanout arbitraire. Mais dans la version randomisée de PolyL, ce n'est pas comme si vous obtenez une bande de bits aléatoires que vous pouvez regarder autant que vous le souhaitez; vous n'êtes plutôt autorisé à lancer une pièce qu'à chaque pas de temps.

Merci!

La plupart des gens pensent peut-être que (ou même que R N C = N C ), mais je suis sceptique à ce sujet (voir la deuxième partie de mon Réponse ci-dessous). Si R N C est bien contenu dans D S P A C E ( p o l y l o g ) , alors il est aussi contenu dans $\mathsf{RNC}\subseteq \mathsf{DSPACE(polylog)}$$\mathsf{RNC}=\mathsf{NC}$$\mathsf{RNC}$$\mathsf{DSPACE(polylog)}$ (plus précisément, c'est dans D T I M E ( 2 p o l y l o g ) par recherche exhaustive).$\mathsf{NTIME(2^{polylog})}$$\mathsf{DTIME(2^{polylog})}$

Valentine Kabanets m'a expliqué l'argument (folklore) suivant de son article avec Russell Impagliazzo qui explique pourquoi est peu probable.$\mathsf{RNC} \subseteq \mathsf{NTIME(2^{polylog})}$

Théorème: Si , alors soit N E X P n'est pas calculable par des circuits booléens de taille o ( 2 n / n ) (c'est-à-dire sous-maxsize par Shannon; non pertinent mais voir Lupanov pour l'étanchéité), ou permanent n'est pas calculable par des formules arithmétiques (sans division) sur$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NEXP}$$o(2^n/n)$ de taille quasipolynomiale.${\mathbb Z}$

Preuve: supposons . Si Permanent a une formule de taille quasipolynomiale, alors nous pouvons deviner et vérifier une telle formule pour Permanent en utilisant un testeur d'identité polynomiale temporelle quasipolynomiale par hypothèse. Cela place permanent dans N T I M E ( 2 p o l y l o g ) .$\mathsf{RNC}\subseteq \mathsf{NTIME(2^{polylog})}$$\mathsf{NTIME(2^{polylog})}$

Selon le théorème de Toda, est alors également dans N T I M E ( 2 p o l y l o g ) . Par foulardage, la version linéaire de temps exponentielle de Σ 5 est également en N E X P . Par conséquent, la version exponentielle linéaire de Σ 5 a un circuit de taille o ( 2 n / n ) (c'est-à-dire submax). Mais, par un simple argument de diagonalisation, on peut montrer que la version exponentielle linéaire de Σ $\Sigma_2$$\mathsf{NTIME(2^{polylog})}$$\Sigma_5$$\mathsf{NEXP}$$\Sigma_5$$o(2^n/n)$$\Sigma_5$nécessite une taille de circuit maximale, ce qui est une contradiction (en passant, c'est une variante d'une question de niveau intermédiaire pour un cours de complexité de niveau supérieur; d'accord, peut-être la preuve que nécessite des circuits de taille maximale est plus simple). QED.$\mathsf{EXPSPACE}$

Maintenant, la direction impopulaire.

Nous savons déjà que l'aléatoire lu plusieurs fois peut faire quelque chose de non évident. Un exemple intéressant peut être trouvé dans « Making Nondeterminism Unambiguous » de Reinhardt et Allender (ils le disent en termes de non-uniformité mais en principe il s'agit d'utiliser le hasard à lecture multiple). Un autre exemple intéressant (moins directement lié) est " Randomness Buys Depth for Approximate Counting " par Emanuele Viola. Je suppose que tout ce que je dis, c'est que je ne serais pas surpris si la dérandomisation de $\mathsf{RNC}$

(Il existe également quelques autres articles, comme le merveilleux article de Noam Nisan sur le caractère aléatoire à lecture unique ou à lecture multiple, qui montrent comment acheter une erreur bilatérale avec une erreur unilatérale.)

Soit dit en passant, comprendre comment construire des PRG trompant les modèles de calcul délimités par l'espace avec plusieurs accès à leur entrée (par exemple des longueurs linéaires Bps) est également très lié à cette question.

- Periklis