Analogue exponentiel de NC?

La classe de Nick (NC) est la classe de problèmes qui peuvent être résolus en temps poly-log en utilisant un nombre polynomial de processeurs.

Je veux en savoir plus sur l'analogue exponentiel, qui couvrirait les problèmes qui peuvent être résolus en temps polynomial en utilisant un nombre exponentiel de processeurs.

Ce que je recherche, c'est un nom pour cette classe et toutes les relations connues entre cette classe et d'autres classes de complexité, ou tout problème canonique pour la classe. Il semble simple qu'il contiendrait du NP et du co-NP, et je pense qu'il est contenu dans PSPACE, mais je ne sais pas grand chose d'autre à ce sujet.

Le temps dans les circuits correspond à la profondeur. Par conséquent, par temps polynomial, on entend la profondeur polynomiale.

Le nombre de processeurs est la taille du circuit, c'est-à-dire le nombre de portes dans le circuit. Donc, par nombre exponentiel de processeurs, vous autorisez une taille exponentielle. Ce serait la classe$\mathsf{DepthSize}(n^{O(1)}, 2^{n^{O(1)}})$. Mais chaque fonction est déjà en$\mathsf{DepthSize}(2, 2^{n^{O(1)}})$ (pensez au CNF de la fonction que vous voulez calculer).

Le point à retenir est que le nombre exponentiel de processeurs est trop fort pour être utile en soi.

Une restriction raisonnable à mettre est de limiter la quantité de communication entre les différents processus. Par exemple, chaque processus ne peut communiquer qu'avec de nombreux autres processus polynomiaux et les messages ont une taille polynomiale. Ce serait$\mathsf{PSpace}$comme expliqué dans les réponses à la question d'Aterm sur la théorie . Une autre façon de le voir pour se souvenir que $\mathsf{PSpace} = \mathsf{ATime}(n^{O(1)})$, problèmes calculables en alternant les machines de Turing en temps polynomial. L'alternance dans les machines de Turing consiste essentiellement à forger de nouveaux processus, puis à les rejoindre après la fin en prenant la conjonction / la disjonction de leurs valeurs de retour.